pku 1948 Triangular Pastures 0-1背包思想
題意：有N個不同長度fence，求用所有fence能組成的最大三角形的面積。
幾天前就看到這個題了，今天才過掉，對這個題感覺非常失敗。
首先第一想法是：將總邊長的三分之一做為背包容量，進(jìn)行一次0-1背包，然后再用剩下的三分之二邊長的一半做背包容量，再進(jìn)行一次0-1背包。但問題是進(jìn)行第一次背包的時候要記錄使用過的邊，以便在第二次背包時不再使用。但由于能力問題，動手寫過兩次都無法解決這個問題。百度一下，發(fā)現(xiàn)人家也想到這個思路，但都被否決了，原因是這樣的思路，通過找三邊差值最小，并不能保證面值最大。
然后我就沒想法了。直到今天，看到marvin（網(wǎng)上認(rèn)識的ACMer）的blog，才知道思路應(yīng)該是這樣的：枚舉第一條邊和第二條邊的組合，用sgn[j][k]標(biāo)記第一邊長為j，第二邊長為k。如果能從給出的邊里組成這兩條邊，則進(jìn)行標(biāo)記。
看到這個思路后，發(fā)現(xiàn)原來就是這么簡單，但怎么自己就沒有想到呢。然后馬上動手就寫，又WA到快吐血。
雖然很快發(fā)現(xiàn)問題出在了用背包枚舉兩邊組合的那幾行代碼，但就是改不過來，在那里糾結(jié)得跳樓的心都有。做了一個星期的背包，居然連這幾行代碼都寫不出，都羞死了。
寫不出那幾個代碼的原因：1，對用背包枚舉兩邊組合的原理理解不透徹。2，沒有認(rèn)真分析組合情況。3，做單純的背包題時留下的思維僵硬。4.，將或運算想當(dāng)然的寫成了并運算。
AC了這個題目后，對背包枚舉兩邊組合部分的三重循環(huán)的邊界條件感覺還是很抽象。再深入去想，才逐漸明了。
1，需要枚舉的兩條邊的長度都是不能超過總長的一半的。
2，由于各邊只能使用一次，同0-1背包，循環(huán)需要用逆序。
3，對于第條邊，如果已有sgn[j-fence[i]][k]或者sgn[j][k-fence[i]]，則必有sgn[j][k]。由于這種組合只需滿足其中一個即可，所以j和k都要枚舉到0并且要保證j>=fence[i]或者k>=fence[i]。
4，優(yōu)化速度的問題。由于j和k可能會出現(xiàn)長度交換時會進(jìn)行重復(fù)計算，所以在計算的時候可以只取j>=k的情況，但枚舉組合的時候能取j>=k進(jìn)行枚舉嗎？表面上對j>=k的情況進(jìn)行過枚舉，似乎就滿足目的了。但實際上，這樣的j>=k的限制導(dǎo)致，能枚舉，但不能有效地標(biāo)記組合。
設(shè)sgn[j0][k0]為確定組合(0<=k0<=j0) （確定組合即為能夠確定這種組合的存在與否）
若k0+fenc[i]>j0時
fence[i]只能加到第一邊，得到確定組合sgn[j0+fence[i]][k0]
當(dāng)fence[i+1]+k0>j0+fence[i]時，(顯然，這時fence[i+1]>fence[i])
fence[i+1]又只能加到第一邊。
這樣sgn[j0+fence[i+1]][k0+fence[i]]的組合就只能標(biāo)記為失敗了。
解決方式是：對于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;
}