这题思路倒是好想，对FJ付款做一次多重背包得到pf[]，对shopkeeper找零做一次完全背包得到rf[]，然后查找min{pf[i]+rf[i-T]}
关键在于shopkeeper的找钱范围的确定。如果不加以限制，其找钱范围能达到10000*100*120，也就是10^8。极其不理想。。。。但是实际上，我们可以发现，其实最大范围也只需要到Vmax*Vmax就绝对够用了。（其实是V的最大值乘以次大值，好像进一步可以到两数的最小公倍数，就足够，然后，考虑这样取要排序，而且如果n==1的话要特殊处理，比较恶。。就多开一点了。。）超过Vmax*Vmax的部分，必然是不超过Vmax*Vmax的一个rf[]加上几个coins得到的。详细证明还真不太好说。。。但是绝对能证明的。。。

另外~单调队列确实有意思。。太好用了。。

• Re:完全背包+多重背包 (407) saintqdd 2011-04-19 22:24:00
• Re:完全背包+多重背包 (34) mountainhigh 2011-05-24 20:42:32
• Re:完全背包+多重背包 (8) 1guangnian 2011-07-16 19:13:17