pku 1948 Triangular Pastures 0-1背包思想

題意：有N個(gè)不同長(zhǎng)度fence，求用所有fence能組成的最大三角形的面積。

幾天前就看到這個(gè)題了，今天才過掉，對(duì)這個(gè)題感覺非常失敗。

首先第一想法是：將總邊長(zhǎng)的三分之一做為背包容量，進(jìn)行一次0-1背包，然后再用剩下的三分之二邊長(zhǎng)的一半做背包容量，再進(jìn)行一次0-1背包。但問題是進(jìn)行第一次背包的時(shí)候要記錄使用過的邊，以便在第二次背包時(shí)不再使用。但由于能力問題，動(dòng)手寫過兩次都無法解決這個(gè)問題。百度一下，發(fā)現(xiàn)人家也想到這個(gè)思路，但都被否決了，原因是這樣的思路，通過找三邊差值最小，并不能保證面值最大。

然后我就沒想法了。直到今天，看到marvin（網(wǎng)上認(rèn)識(shí)的ACMer）的blog，才知道思路應(yīng)該是這樣的：枚舉第一條邊和第二條邊的組合，用sgn[j][k]標(biāo)記第一邊長(zhǎng)為j，第二邊長(zhǎng)為k。如果能從給出的邊里組成這兩條邊，則進(jìn)行標(biāo)記。

看到這個(gè)思路后，發(fā)現(xiàn)原來就是這么簡(jiǎn)單，但怎么自己就沒有想到呢。然后馬上動(dòng)手就寫，又WA到快吐血。

雖然很快發(fā)現(xiàn)問題出在了用背包枚舉兩邊組合的那幾行代碼，但就是改不過來，在那里糾結(jié)得跳樓的心都有。做了一個(gè)星期的背包，居然連這幾行代碼都寫不出，都羞死了。

寫不出那幾個(gè)代碼的原因：1，對(duì)用背包枚舉兩邊組合的原理理解不透徹。2，沒有認(rèn)真分析組合情況。3，做單純的背包題時(shí)留下的思維僵硬。4.，將或運(yùn)算想當(dāng)然的寫成了并運(yùn)算。

AC了這個(gè)題目后，對(duì)背包枚舉兩邊組合部分的三重循環(huán)的邊界條件感覺還是很抽象。再深入去想，才逐漸明了。

1，需要枚舉的兩條邊的長(zhǎng)度都是不能超過總長(zhǎng)的一半的。

2，由于各邊只能使用一次，同0-1背包，循環(huán)需要用逆序。

3，對(duì)于第條邊，如果已有sgn[j-fence[i]][k]或者sgn[j][k-fence[i]]，則必有sgn[j][k]。由于這種組合只需滿足其中一個(gè)即可，所以j和k都要枚舉到0并且要保證j>=fence[i]或者k>=fence[i]。

4，優(yōu)化速度的問題。由于j和k可能會(huì)出現(xiàn)長(zhǎng)度交換時(shí)會(huì)進(jìn)行重復(fù)計(jì)算，所以在計(jì)算的時(shí)候可以只取j>=k的情況，但枚舉組合的時(shí)候能取j>=k進(jìn)行枚舉嗎？表面上對(duì)j>=k的情況進(jìn)行過枚舉，似乎就滿足目的了。但實(shí)際上，這樣的j>=k的限制導(dǎo)致，能枚舉，但不能有效地標(biāo)記組合。

設(shè)sgn[j0][k0]為確定組合(0<=k0<=j0)  （確定組合即為能夠確定這種組合的存在與否）

若k0+fenc[i]>j0時(shí)

fence[i]只能加到第一邊，得到確定組合sgn[j0+fence[i]][k0]

當(dāng)fence[i+1]+k0>j0+fence[i]時(shí)，(顯然，這時(shí)fence[i+1]>fence[i])

fence[i+1]又只能加到第一邊。

這樣sgn[j0+fence[i+1]][k0+fence[i]]的組合就只能標(biāo)記為失敗了。

解決方式是：對(duì)于fence[i]，只要第一邊不使用這個(gè)fence[i]的時(shí)候，必須要讓它能夠加到第二邊。這樣去k=j+fence[i]即可。