说下我的思路,欢迎拍砖:
/*类似于背包的dp.不过做了点优化
设dp的是价值为i的大理石.个数为num[i]个,最外面对i进行dp,然后容量j是从大到小dp
如果容量j是可行的那么 j+k*i (1<=k<=num[i])都是可行的.所以在要有一个循环:
k从1 到 num[i]的循环,但是仔细想一想,如果j+k*i 发现已经可行的话,接下来就可以
跳出循环了.因为j+k*i可行,是之前的j0+k0*i让他可行的(或者本身就行了).
而j0>j,可知:k0<k.  所以剩下可以用的石子更多,已经把后面的can[]弄成1了.
这个优化:TLE -> 0ms*/
代码见:
http://hi.baidu.com/bluesea258/blog/item/13c65436b747cfd0a2cc2ba1.html