相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4374
神犇题解:http://www.cnblogs.com/clrs97/p/6371735.html
解题报告
这题如果钱的总数小一点就可以直接DP了
于是我就想到了这个题:BZOJ 2749
于是我们就可以把钱给离散化到900以内啦!
但这样我们没有办法进行转移,然后就不会了 QwQ
不过万能的Claris告诉我们,物品只有30个
于是我们可以折半暴搜,这样的话就不需要转移了
直接枚举左侧的值,右侧搞一个指针跟着动一动就好
时间复杂度: $O(nm{2^{\frac{n}{2}}} + n{m^2})$