首页 > > 程序设计 > C/C++ >

Triangular Pastures POJ - 1948

2018-06-17 21:35:46来源：未知阅读 ()

sum表示木条的总长。a[i]表示第i根木条长度。ans[i][j][k]表示用前i条木条，摆成两条长度分别为j和k的边是否可能。

那么ans[i][j][k]=ans[i-1][j-a[i]][k] || ans[i-1][j][k-a[i]]

可以用滚动数组优化。

最后在ans[n]中枚举i和j，如果ans[n][i][j]为true，再算出sum-i-j的长度，判断是否存在分别以i,j,sum-i-j为三边长的三角形。如果存在，再用海伦公式算出三角形面积，用面积去更新最大面积。

错误记录：
没有在dp的时候判边界，也就是没有判j>=a[i]和k>=a[i]。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 bool ans[1601][1601];
 7 LL a[41],n,sum;
 8 double p,anss;
 9 int main()
10 {
11     LL i,j,k,x,y,z;
12     scanf("%lld",&n);
13     for(i=1;i<=n;i++)
14     {
15         scanf("%lld",&a[i]);
16         sum+=a[i];
17     }
18     ans[0][0]=1;
19     for(i=1;i<=n;i++)
20         for(j=sum;j>=0;j--)
21             for(k=sum;k>=0;k--)
22             {
23                 if(j>=a[i])
24                     ans[j][k]|=ans[j-a[i]][k];
25                 if(k>=a[i])
26                     ans[j][k]|=ans[j][k-a[i]];
27             }
28     for(x=1;x<=sum;x++)
29         for(y=x;y<=sum-x-1;y++)
30         {
31             if(!ans[x][y])    continue;
32             z=sum-x-y;
33             if(y>z)    break;
34             if(x+y<=z) continue;
35             p=(double)(x+y+z)/2.0;
36             anss=max(anss,sqrt(p*(p-x)*(p-y)*(p-z)));
37         }
38     if(anss!=0.0)
39         printf("%lld",(long long)(anss*(double)100));
40     else
41         printf("-1");
42     return 0;
43 }