PKU1837-Balance

題目：http://poj.org/problem?id=1837
天秤上有C(20)個刻度點(-15...15)
想要把G(20)顆重量為wi(1...25)的砝碼全部掛上去
問達成兩邊平衡的"方法數"有幾種


程式碼(有瑕疵)：http://codepad.org/b7yetB64

其實本質就是一個子集合加總問題
然而總和範圍是確定的：
最大(或最小)只會是10顆重25的砝碼擺在刻度15/-15上，-3750...3750
利用總和範圍來進行DP

據此定義數組DP[x][y+4000]代表放了前x個砝碼後，天秤總重y的方法數
最後DP[G][4000]就是答案

寫到這裡發現我程式碼沒有砍掉超出(不可能達成平衡)的狀況、還是過了
可見數據之弱