pku 1948 Triangular Pastures 0-1背包思想
题意：有N个不同长度fence，求用所有fence能组成的最大三角形的面积。
几天前就看到这个题了，今天才过掉，对这个题感觉非常失败。
首先第一想法是：将总边长的三分之一做为背包容量，进行一次0-1背包，然后再用剩下的三分之二边长的一半做背包容量，再进行一次0-1背包。但问题是进行第一次背包的时候要记录使用过的边，以便在第二次背包时不再使用。但由于能力问题，动手写过两次都无法解决这个问题。百度一下，发现人家也想到这个思路，但都被否决了，原因是这样的思路，通过找三边差值最小，并不能保证面值最大。
然后我就没想法了。直到今天，看到marvin（网上认识的ACMer）的blog，才知道思路应该是这样的：枚举第一条边和第二条边的组合，用sgn[j][k]标记第一边长为j，第二边长为k。如果能从给出的边里组成这两条边，则进行标记。
看到这个思路后，发现原来就是这么简单，但怎么自己就没有想到呢。然后马上动手就写，又WA到快吐血。
虽然很快发现问题出在了用背包枚举两边组合的那几行代码，但就是改不过来，在那里纠结得跳楼的心都有。做了一个星期的背包，居然连这几行代码都写不出，都羞死了。
写不出那几个代码的原因：1，对用背包枚举两边组合的原理理解不透彻。2，没有认真分析组合情况。3，做单纯的背包题时留下的思维僵硬。4.，将或运算想当然的写成了并运算。
AC了这个题目后，对背包枚举两边组合部分的三重循环的边界条件感觉还是很抽象。再深入去想，才逐渐明了。
1，需要枚举的两条边的长度都是不能超过总长的一半的。
2，由于各边只能使用一次，同0-1背包，循环需要用逆序。
3，对于第条边，如果已有sgn[j-fence[i]][k]或者sgn[j][k-fence[i]]，则必有sgn[j][k]。由于这种组合只需满足其中一个即可，所以j和k都要枚举到0并且要保证j>=fence[i]或者k>=fence[i]。
4，优化速度的问题。由于j和k可能会出现长度交换时会进行重复计算，所以在计算的时候可以只取j>=k的情况，但枚举组合的时候能取j>=k进行枚举吗？表面上对j>=k的情况进行过枚举，似乎就满足目的了。但实际上，这样的j>=k的限制导致，能枚举，但不能有效地标记组合。
设sgn[j0][k0]为确定组合(0<=k0<=j0) （确定组合即为能够确定这种组合的存在与否）
若k0+fenc[i]>j0时
fence[i]只能加到第一边，得到确定组合sgn[j0+fence[i]][k0]
当fence[i+1]+k0>j0+fence[i]时，(显然，这时fence[i+1]>fence[i])
fence[i+1]又只能加到第一边。
这样sgn[j0+fence[i+1]][k0+fence[i]]的组合就只能标记为失败了。
解决方式是：对于fence[i]，只要第一边不使用这个fence[i]的时候，必须要让它能够加到第二边。这样去k=j+fence[i]即可。
#include <iostream>
#include <math.h>
using namespace std;
const int MAX=800;
bool sgn[MAX+1][MAX+1];
int fence[41];
int main()
{
double find(int,int,int);
int i,j,k,n,sum=0;
scanf("%d",&n);
for(i=1;i<=n;++i) {scanf("%d",&fence[i]);sum+=fence[i];}
memset(sgn,0,sizeof(sgn));
sgn[0][0]=1;
for(i=1;i<=n;++i)
for(j=sum/2;j>=0;--j)
for(k=j+fence[i];k>=0;--k)
if((j>=fence[i]&&sgn[j-fence[i]][k])||
(k>=fence[i]&&sgn[j][k-fence[i]]))
sgn[j][k]=1;
double ans=-0.01,tmp;
for(i=1;i<=sum/2;++i)
for(j=1;j<=i;++j)
if(sgn[i][j])
{
tmp=find(sum-i-j,i,j);
ans=ans>tmp?ans:tmp;
}
cout<<int(ans*100)<<endl;
return 0;
}
double find(int x,int y,int z)
{
if(x+y>z&&x+z>y&&y+z>x)
return sqrt(1.0*(x+y+z)*(x+y-z)*(x+z-y)*(y+z-x))*0.25;
else
return -0.01;
}