hdu6196 happpy happy happy (meet in middle + 剪枝)
题意
从1到n共计n(<=90)个物品,每个物品有一个价值a[i],儿子和爸爸轮流做游戏,儿子先手。儿子每次选价值最大的{最左边,最右边}的物品,如果价值一样大, 则选取最左边的物品。 爸爸每次可以取最左边或最右边的物品。
问你,爸爸想要输(价格严格小),而且差值尽可能少的最小差值是多少。
分析
首先n<=90,所以应该是个搜索,而不是dp
我们来考虑一下为什么不是dp,而只能搜索?
如果题目改成爸爸想让差值最大或者最小,那么显然可以直接dp,而这里实际上求一个大于0的最小差值,相当于在所有可能差值的中间,自然无法dp了
直接dfs显然时间效率是$O(2^{45})$无法接受,这里可以考虑meet in middle,我们将90个物品分成44个和46个
对于里面的部分,我们可以先dfs求出所有可能差值,然后再dfs外面,如果当前长度<=44了,那么我们就可以将当前结果在之前第一次dfs的结果里二分,找到大于0的最小差值
这样时间复杂度就是$O(2^{23}*log(2^{22}))$
这样的时间复杂度感觉勉强是可以接受的,但问题是,2^22这么多取值我们无法存进数组中
那我们只有加大两部分的差值了,比如提前预处理长度为30的结果,再去对长度为50的dfs
但这样的话,对50的dfs部分时间复杂度是$O(2^{25}*log(2^{15}))$,我们必须剪枝
对于dfs(l,r),有两个剪枝:
如果当前差值+[l,r]最大差值<=0,这说明这种情况儿子始终无法赢,直接return
如果当前差值+[l,r]最小差值>=ans,这说明这种情况下的结果不会比ans更优,直接return
加上这两个剪枝就可以1800ms通过了
最新文章
- sql server 权限体系
- Codeforces Round #251 (Div. 2) C. Devu and Partitioning of the Array
- 正确停止kafka的方法
- wxPython
- 调用数据库过程函数mysql
- (转)iOS7界面设计规范(2) - UI基础 - iOS应用解析
- Android测试TestSuite的执行方法
- [Unity3D]Unity3D游戏开发Lua随着游戏的债券(于)
- 命令行解决mysql中文乱码
- Chrome浏览器扩展开发系列之九:Chrome浏览器的chrome.alarms.* API
- SQL Server 审计操作概念
- Android接受验证码自动填入功能(源码+已实现+可用+版本兼容)
- Android Multimedia框架总结(十四)Camera框架初识及自定义相机案例
- IDEA编写css样式报错
- MyDAL - .QueryListAsync() 使用
- js面向对象学习
- tornado websocket聊天室
- Connection reset by peer原理解析
- https 不检验证书
- 干净的ssm框架项目