题目链接：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)