设dp[i][j]为用前i种钱币，最少使用多少个第i种钱币的情况下可以凑出j个单位的钱。

加上一个滚动数组

if (dp[j]!=-1)dp[j]=0;
else if (j>=A[i] && dp[j-A[i]]!=-1 && dp[j-A[i]]<C[i])dp[j]=dp[j-A[i]]+1;
else dp[j]=-1;

• Re:竟然让一个普通的多重背包用了18xx秒很顺利地过了 (216) endkiller 2010-10-04 00:15:21