題意
給出一些木棒，問能否用這些木棒拼成三角形，如果可能求最大的面積。
解法：
先給出一個定理：海倫公式
下面就是枚舉邊長。首先枚舉最長邊c，由于兩邊之和大于第三邊，c的長度必須小于周長的一半，這是一個重要的剪枝。如果還要剪枝，可以先一次DP求得由木棍組合可以達(dá)到的長度。
確定c以后再枚舉a，然后再次可以用DP驗證木棒能否組合成a、c的長度。這里可以再一次剪枝，枚舉c的時候建議從周長的一半向下枚舉，原因很簡單，盡量構(gòu)造一個較優(yōu)的合法解，根據(jù)海倫公式(p-a)(p-b)(p-c)，當(dāng)c確定時最大值的位置也清楚了（b和c相等的位置，如果在最優(yōu)位置（上限，可能達(dá)不到）都不能比最優(yōu)解優(yōu)，就直接cut）。然后下面就沒什么難度了。
代碼：
1 # include <cstdio>
2 # include <cstring>
3 # include <cstdlib>
4 # include <cmath>
5 using namespace std;
6 # include <algorithm>
7 bool dp[2][855][855];
8 int plen[1605],pc=0;
9 int n,len[41];
10
11 int main()
12 {
13 int total=0;
14 scanf("%d",&n);
15 for(int i=0;i<n;i++)
16 {
17 scanf("%d",len+i);
18 total+=len[i];
19 }
20 sort(len,len+n);
21 bool tmp[1606];
22 memset(tmp,false,sizeof(tmp));
23 memset(dp[0],0,sizeof(dp[0]));
24 dp[0][0][0]=true;
25 for(int i=1;i<=n;i++)
26 {
27 memset(dp[i%2],false,sizeof(dp[i%2]));
28 for(int j=0;j<=total/2+40;j++)
29 for(int k=j;k<=total/2+40;k++)
30 if(j-len[i-1]>=0&&dp[(i-1)%2][min(j-len[i-1],k)][max(j-len[i-1],k)]||
31 k-len[i-1]>=0&&dp[(i-1)%2][min(j,k-len[i-1])][max(k-len[i-1],j)]||
32 dp[(i-1)%2][j][k])
33 dp[i%2][j][k]=true;
34 }
35
36 tmp[len[0]]=true;
37 for(int i=1;i<n;i++)
38 for(int j=0;j<=total;j++)
39 if(tmp[j]&&j+len[i]<=total)
40 tmp[j+len[i]]=true;
41 for(int i=0;i<=total;i++)
42 if(tmp[i])
43 plen[pc++]=i;
44 int best=-1;
45 for(int c=lower_bound(plen,plen+pc,total/2)-plen-1;c>=0;c--)
46 {
47 int a=(total-plen[c])/2,b=total-plen[c]-a;
48 if(best!=-1&&(total-2*plen[c])*(total-2*a)*(total-2*b)<best) continue;
49 for(a=0;plen[a]<total-plen[c];a++)
50 if(plen[c]>=plen[a]&&plen[c]>=total-plen[a]-plen[c]&&dp[n%2][plen[a]][plen[c]]&&(best==-1||best<(total-2*plen[c])*(total-2*plen[a])*(total-2*(total-plen[a]-plen[c]))))
51 best=(total-2*plen[c])*(total-2*plen[a])*(total-2*(total-plen[a]-plen[c]));
52 }
53 if(best==-1) printf("-1\n");
54 else
55 {
56 best=(int)(sqrt(best*(double)total)*25+1e-6);
57 printf("%d\n",best);
58 }
59 //system("pause");
60 return 0;
61
62 }
63