PKU1015-Jury Compromise

題目：http://poj.org/problem?id=1015
有n個人要選m個人當陪審團(n<=200,m<=20)
每個人對控方和辯方有不同的好感度(這些值介於0...20)
給出一種陪審團組合滿足 | "控方總好感"-"辯方總好感" | 最小，
並且 "控方總好感"+"辯方總好感" 最大

(之前這篇還沒補上內容的時候google "pku 1015"就會連進來了...真可怕QQ)


程式碼：http://codepad.org/Agd2tb1t
一年多前從pku經典50題上看到的DP題目
今天又重新code一遍，果然是很不錯適合新手的一道題
它之所以能DP的重點，和背包問題頗像：好感值致多是20
因為只選20個人，所以結論出來的差距值只有-400到+400
抓著這個點就能進行DP

設計狀態DP[選了i個人][(差值+400)]={已選取人選 , 好感總和}
定義DP[0][400]={全不選 , 0}
然後依選的人->差值->未選人選進行遞推

不過這算法的正確性在我心目中還是比較模糊的：被捨棄的狀態為何能捨棄？
拿這組測資來說
5 4
2 3
3 4
4 5
5 6
6 7
0 0
假設現在已經有DP[2][398]={ {4,5} , 24}，
通過人1、人2和人3都能造出DP[3][397]的值，這時人1人2的可能性就被捨棄了
我想
總差距最小是先決要件(差距相同都落到397這個狀態，否則會錯開)
相互碰撞就能代表這三位候選人單獨的差距都是一樣的：-1
所以在人數只能取一的情形下顯然取總和高的才符合要求
等到考慮選取人數3->4的時候自然會重新試人1和人2的可能性

小結：
我想DP強大的地方就在於"列舉全狀態"、"每次轉移只考慮一個物件"
其中列舉全狀態需要題設上給予時空方面的方便
然而每次轉移的部分，
我認為和一般人在紙上手算手推的方法是很神似的
就算不是DP解決的問題，
說不定也會因為一開始嘗試了DP思路而通往正確解答呢