POJ 1948 Triangular Pastures(二维背包) - ACway的专栏 - 博客频道 - CSDN.NET
http://shangxun.iteye.com/blog/1937614
Like everyone, cows enjoy variety. Their current fancy is new shapes for pastures. The old rectangular shapes are out of favor; new geometries are the favorite.
I. M. Hei, the lead cow pasture architect, is in charge of creating a triangular pasture surrounded by nice white fence rails. She is supplied with N (3 <= N <= 40) fence segments (each of integer length Li (1 <= Li <= 40) and must arrange them into a triangular pasture with the largest grazing area. Ms. Hei must use all the rails to create three sides of non-zero length.
Help Ms. Hei convince the rest of the herd that plenty of grazing land will be available.Calculate the largest area that may be enclosed with a supplied set of fence segments.
I. M. Hei, the lead cow pasture architect, is in charge of creating a triangular pasture surrounded by nice white fence rails. She is supplied with N (3 <= N <= 40) fence segments (each of integer length Li (1 <= Li <= 40) and must arrange them into a triangular pasture with the largest grazing area. Ms. Hei must use all the rails to create three sides of non-zero length.
Help Ms. Hei convince the rest of the herd that plenty of grazing land will be available.Calculate the largest area that may be enclosed with a supplied set of fence segments.
Input
* Line 1: A single integer N
* Lines 2..N+1: N lines, each with a single integer representing one fence segment's length. The lengths are not necessarily unique.
* Lines 2..N+1: N lines, each with a single integer representing one fence segment's length. The lengths are not necessarily unique.
Output
A single line with the integer that is the truncated integer representation of the largest possible enclosed area multiplied by 100. Output -1 if no triangle of positive area may be constructed.
Sample Input
5 1 1 3 3 4
Sample Output
692
Hint
[which is 100x the area of an equilateral triangle with side length 4]
题意:
求n条线段构成的三角形的最大面积*100
题解
由于三角形有三个边,并且所有的线段都要用到,于是可以用dp[i][j]表示边长为i,j,sum-i-j的三角形,由于是二维的,j,k边有一个可以取到0,另一个减去a后要大于等于0,最后用海伦公式算面积。
http://shangxun.iteye.com/blog/1937614
f[i][j][k] 表示用前i条边,能否组成长度为j和k的两条边
初始化f[0][0][0] = true;
f[i][j][k] = f[i-1][j-len[i]][k] || f[i-1][j][k-len[i]];
如果f[i][j][k]=true,那么就计算以j,k,sum-j-k为三条边能否组成三角形,如果可以就用海伦公式计算面积。
由于如果要开三维数组的话,要开f[40][1600][1600],明显是要MLE的,所以要降成二维的,
而时间复杂度40*1600*1600,如果没有优化直接上,是要TLE的。
所以要优化,根据优化的程度,运行时间可以再100MS~1000MS之间:
初始化f[0][0][0] = true;
f[i][j][k] = f[i-1][j-len[i]][k] || f[i-1][j][k-len[i]];
如果f[i][j][k]=true,那么就计算以j,k,sum-j-k为三条边能否组成三角形,如果可以就用海伦公式计算面积。
由于如果要开三维数组的话,要开f[40][1600][1600],明显是要MLE的,所以要降成二维的,
而时间复杂度40*1600*1600,如果没有优化直接上,是要TLE的。
所以要优化,根据优化的程度,运行时间可以再100MS~1000MS之间:
1. f[i][j] 和 f[j][i]是相同的两个三角形,所以递推时可以让 j>=i
2. 对于每条边,一定是小于周长的一半
3. 枚举到第i条边时, 前i条边不可能组成大于等于sum[i] (sum[i]=len[1]+...+len[i])的长度
2. 对于每条边,一定是小于周长的一半
3. 枚举到第i条边时, 前i条边不可能组成大于等于sum[i] (sum[i]=len[1]+...+len[i])的长度
- inline bool isTriangle(double e[3]){
- if(e[2] < e[1]){
- swap(e[2], e[1]);
- if(e[1] < e[0]) swap(e[0], e[1]);
- }
- return e[0]+e[1] > e[2];
- }
- inline double getArea(double e[3]){
- if(!isTriangle(e)) return -1;
- double p = sum[n]/2.0;
- return sqrt(p*(p-e[0])*(p-e[1])*(p-e[2]));
- }
- int main(){
- scanf("%d", &n);
- for(int i=1; i<=n; ++i){
- scanf("%d", &len[i]);
- sum[i] = sum[i-1]+len[i];
- }
- memset(f, 0, sizeof(f));
- f[0][0] = true;
- double ans = -1;
- double e[3];
- for(int i=1; i<=n; ++i){
- for(int v1=min(sum[i],sum[n]>>1); v1>=0; --v1){
- for(int v2=min(sum[i]-v1,sum[n]>>1); v2>=v1; --v2)if(v1+v2<sum[n]){
- e[0] = v1; e[1] =v2; e[2] = sum[n]-v1-v2;
- if(v1-len[i]>= 0 && f[v1-len[i]][v2]){
- f[v1][v2] = true;
- }
- if(!f[v1][v2] && v2-len[i]>=0 && f[v1][v2-len[i]]){
- f[v1][v2] = true;
- }
- if(f[v1][v2]){
- ans = max(ans, getArea(e));
- }
- }
- }
- }
- if(ans < 0) puts("-1");
- else printf("%d\n", (int)(100*ans));
- return 0;
- }
先求面积,用海伦公式,s=sqrt(p*(p-a)*(p-b)*(p-c)),其中a,b,c分别为三角形的三条边,p为三角形的半周长,同时由这个根式可以推出,三角形的任意一条边小于其半周长(根号里面大于0,如果等于0面积为0没有意义了)
所以考虑背包两条边,再用周长减去这两条边求出第三条边,再遍历一遍找出最大的三角形。
dp[i][j]表示三角形的第一条边为i,第二条边为j所构成的三角形是否存在,
如果存在,dp[i][j]=1,否则为0 当dp[i][j]=1的时候,dp[i+l[k]][j]和dp[i][j+l[k]]也为1
19 while(scanf("%d",&n)!=EOF) 20 { 21 int sum=0, ans=-1; 22 for(i=1;i<=n;i++) {scanf("%d",&l[i]);sum+=l[i];} 23 memset(dp,0,sizeof(dp)); 24 dp[0][0]=1; 25 c=sum; 26 sum=c/2-(c/2==0); 27 28 for(k=1;k<=n;k++) 29 for(i=sum;i>=0;i--) 30 for(j=i;j>=0;j--) 31 if(dp[i][j]) dp[i][j+l[k]]=dp[i+l[k]][j]=1; 32 33 for(i=sum;i>=1;i--) 34 for(j=i;j>=1;j--) 35 if(dp[i][j]) ans=max(ans,area(i,j,c-i-j)); 36 printf("%d\n",ans); 37 }Read full article from POJ 1948 Triangular Pastures(二维背包) - ACway的专栏 - 博客频道 - CSDN.NET