星空 题意转化,差分,状压DP
2024-09-01 17:01:17
好题(爆搜和puts("2")一个分(雾)),不得不说思维真的强。
首先发现区间翻转很难受,考虑用差分(异或满足可逆性),注意是从0到n+1
然后就转化题意,操作改为选取距离为L的两个数异或1,我们需要把所有的1变成0(因为1代表前后两个数不同,0代表相同)
分情况考虑
不可能同时让两个0异或成1,所以:
1.一个0,一个1可以视为将1移动到0的位置
2.两个1可以认为将它俩全部消除
考虑一下可以bfs预处理出两个1消除的代价,时间复杂度O(nmk)。
进一步转化题意:
给定n个物品,每两个物品的消除都有一定代价,最小花费?
这就是普通的状压了,但要注意区分O(k*2^2k)和(k^2*2^2k)的打法
具体k*2^k的打法:
对于当前状态state,随便固定一个点,再枚举它和哪些物品同时消除,取min即可
这样做的话,相当于转移的时候只会转移固定一个点的状态,但实际上如果k^2枚举的话会有很多冗余状态,
一个state可以由k个last更新,就冗余啦。
最新文章
- PL/0编译器实践---后记
- CC2540串口输出调试功能
- 动态加载JS 和 CSS
- backtrack下vim的使用
- django 1.7+ default_permissions
- Excel文件操作方式比较
- Winform学习手册(目录)
- Protobuf语言指南
- 我的开发框架(WinForm)4
- 【转】monkeyrunner学习总结二:连接、安装、启动
- 100个常用的linux命令
- rsync实现文件备份同步(比如服务器镜像)
- Longest Palindromic Substring - 一题多解
- mac下面xcode+ndk7配置cocos2dx &; box2d的跨ios和android平台的游戏教程
- suricata 配置文件threshold
- javase中javax源码下载地址
- 第一个ASP.NET Web API (C#)程序
- VMware 导出镜像文件供 Virtual Box 使用
- java使用POI实现excel文件的读取,兼容后缀名xls和xlsx
- AIX修改时区,配置NTP服务