携程员工运动会场地问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 821 Accepted Submission(s): 231
Problem Description
携程每年要举行员工运动会,现在需要搭建三角形的场地给运动员们自由活动。
现在有N (3 <= N <= 40)个栅栏段(每个栅栏长度Li (1 <= Li <= 40)),必须刚好用掉所有的栅栏拼成一个最大面积的三角形活动区域,
求这个最大面积。
现在有N (3 <= N <= 40)个栅栏段(每个栅栏长度Li (1 <= Li <= 40)),必须刚好用掉所有的栅栏拼成一个最大面积的三角形活动区域,
求这个最大面积。
Input
* 第一行: 整数 N ,表示有多少个栅栏
* 第 2..N+1行: 共N 行, 每行中包括一个整数, 表示 一个栅栏的长度.( 多个栅栏的长度可以出现相同).
* 第N+3行:第二组数据。
每组数据隔一空行,文件末尾以0结尾。
* 第 2..N+1行: 共N 行, 每行中包括一个整数, 表示 一个栅栏的长度.( 多个栅栏的长度可以出现相同).
* 第N+3行:第二组数据。
每组数据隔一空行,文件末尾以0结尾。
Output
每行输出一个截取后的整数,即最大面积乘以100后的整数。 如果无法构成,输出 -1。
Sample Input
5
1 1 3 3 4
5
12 37 1 4 3 0
Sample Output
692
-1
一道简单的二维背包问题,当时由于有一段时间没有碰这种题,在做这道题的时候也没有向这个方向想....
并只以为很装B的用着组合数字里的,frrerrs图像可以AC。。。但是最后wa的一塌糊涂....
谢安贴一下错误的代码吧....以此为戒.
代码:
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<vector> 6 #include<math.h> 7 #include<iostream> 8 #include<functional> 9 using namespace std; 10 int main() 11 { 12 int n,i; 13 double ans,tol; 14 //freopen("test.in","r",stdin); 15 //freopen("test.out","w",stdout); 16 while(scanf("%d",&n)!=EOF) 17 { 18 vector<int>aa(n+1); 19 for(i=0;i<n;i++) 20 cin>>aa[i]; 21 sort(aa.begin(),aa.end(),greater<int>()); 22 for(i=3;i<n;i++) 23 { 24 if(aa[0]>aa[1]) 25 { 26 if(aa[1]>aa[2]) 27 aa[2]+=aa[i]; 28 else 29 aa[1]+=aa[i]; 30 } 31 else 32 { 33 if(aa[0]>aa[2]) 34 aa[2]+=aa[i]; 35 else 36 aa[0]+=aa[i]; 37 } 38 } 39 tol=(aa[0]+aa[1]+aa[2])/2.0; 40 ans=(100.0*sqrt(tol*(tol-aa[0])*(tol-aa[1])*(tol-aa[2]))); //o£?×1?ê? 41 if(ans>1.0e-4) 42 { 43 printf("%d %d %d ",aa[0],aa[1],aa[2]); 44 printf("%.lf ",floor(ans)); 45 46 } 47 else 48 printf("-1 "); 49 } 50 return 0; 51 }
当然上面的代码,一般的情况是可以过的,但是有bug.....
比如下面的数据就过不了...
1 /* 2 10 3 1 3 6 9 0 8 5 7 4 2 4 7 6 5 4 3 2 1 0 5 1 0 6 2 1 0 7 3 2 1 0 8 4 3 2 1 0 9 5 4 3 2 1 0 10 6 5 4 3 2 1 0 11 7 6 5 4 3 2 1 0 12 8 7 6 5 4 3 2 1 0 13 9 8 7 6 5 4 3 2 1 0 14 10 9 8 7 6 5 4 3 2 1 0 15 */ 16 17 //answer 18 /* 19 9742 20 2121 21 -1 22 -1 23 -1 24 -1 25 447 26 1082 27 2121 28 3741 29 6235 30 9742 31 */
用二维0/1背包来求解为:
当然是经过优化后的...
1 //二维0/1背包 2 //扩大栈空间 3 #pragma comment(linker, "/STACK:102400000,102400000") 4 #include<stdio.h> 5 #include<math.h> 6 #include<string.h> 7 #include<stdlib.h> 8 int val[41],aa[41]; 9 bool dp[801][801]; 10 int main() 11 { 12 int n,i,j,k,ans,len,temp; 13 double cc; 14 freopen("test.in","r",stdin); 15 freopen("test.out","w",stdout); 16 while(scanf("%d",&n)!=EOF) 17 { 18 memset(dp,0,sizeof(dp)); 19 memset(aa,0,sizeof(aa)); 20 for(i=1;i<=n;i++) 21 { 22 scanf("%d",&val[i]); 23 aa[i]+=aa[i-1]+val[i]; 24 } 25 cc=aa[n]/2.0; 26 len=cc; 27 temp=0; 28 dp[0][0]=true; 29 for(i=1;i<=n;i++) 30 { 31 if(len<=aa[i]) 32 temp=len; 33 else temp=aa[i]; 34 for(j=temp;j>=0;j--) 35 { 36 for(k=temp;k>=0;k--) 37 { 38 if((j-val[i]>=0&&dp[j-val[i]][k])||(k-val[i]>=0&&dp[j][k-val[i]])) 39 dp[j][k]=true; 40 } 41 } 42 } 43 ans=0; 44 for(i=1;i<=len;i++) 45 { 46 for(j=1;j<=len;j++) 47 { 48 if(dp[i][j]) 49 { 50 if(ans<100*sqrt(cc*(cc-i)*(cc-j)*(i+j-cc))) 51 ans=100*sqrt(cc*(cc-i)*(cc-j)*(i+j-cc)); 52 } 53 } 54 } 55 if(ans==0) printf("-1 "); 56 else printf("%d ",ans); 57 } 58 return 0; 59 }