题意
给出一些木棒，问能否用这些木棒拼成三角形，如果可能求最大的面积。
解法：
先给出一个定理：海伦公式
下面就是枚举边长。首先枚举最长边c，由于两边之和大于第三边，c的长度必须小于周长的一半，这是一个重要的剪枝。如果还要剪枝，可以先一次DP求得由木棍组合可以达到的长度。
确定c以后再枚举a，然后再次可以用DP验证木棒能否组合成a、c的长度。这里可以再一次剪枝，枚举c的时候建议从周长的一半向下枚举，原因很简单，尽量构造一个较优的合法解，根据海伦公式(p-a)(p-b)(p-c)，当c确定时最大值的位置也清楚了（b和c相等的位置，如果在最优位置（上限，可能达不到）都不能比最优解优，就直接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