BZOJ 4800 [Ceoi2015]Ice Hockey World Championship

发布于 2017-06-17  145 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4800

题意:有 n 个物品,m 块钱,给定每个物品的价格,求买物品的方案数...


终于做到一道 meet-in-the-middle 了... 找题不容易呀

考虑判断一个方案是否合法就是判断总价格是否买得起,然而直接暴搜是\(O(2^n)\) 的... 无法接受

于是对于前 20 个和后 20 个物品分别暴搜,分别记录价格,用两个栈储存,接下来只要两边任取一组价格和小于等于 m 即是一组合法方案

但是暴力枚举的复杂度还是不能接受的... 对两个价格数组排序后维护双指针就好啦,复杂度\(O(2^{n/2}*log_{n/2})\)

 


一个非常弱的准退役OIER