BZOJ 4800 [Ceoi2015]Ice Hockey World Championship


题目链接: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})\)

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4800 [Ceoi2015]Ice Hockey World Championship


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,