題目連結：http://poj.org/problem?id=1742
有nnn種面值不同的硬币，每種有c[i]c[i]c[i]個。求1到mmm有多少面值可以用這些硬币湊成？
很明顯的完全背包。。。
前面WA,TLE,RE,CEWA,TLE,RE,CEWA,TLE,RE,CE全是用二進制拆分做的。。。後來實在沒辦法打了書上的方法。
設f[i]f[i]f[i]為面值為iii可否得到。那麼最基本的O(tnm2)O(tnm^2)O(tnm2)肯定是過不了的。需要優化。
設used[i]used[i]used[i]表示面值湊到iii的最小硬币使用數，那麼我們就可以省掉一重循環，因為，可以用usedusedused來進行最小答案的判斷。
最終答案為∑i=1nf[i]\sum^{n}_{i=1}f[i]∑i=1nf[i]
時間複雜度：O(tnm)O(tnm)O(tnm)