状态压缩DP 小结

发布于 2017-05-25  2.07k 次阅读


(题外话)

嗯,刚刚在调K,然后电脑挂了,程序运行居然关不掉,大概思路已经差不多了额,就先挖个坑,以后回家再调。。。

 

状压DP,主要就是把很难表示的DP过程中的状态压到一个int里,给这个数的每个二进制位赋予一个含义,感觉有点像以前DFS、回溯时候那个bool数组的作用。

状压的题数据范围一般比较有特点,就是在给定1s的情况下,需要压得那个状态一般都在18、19位以下,所以遇到题的时候可以根据这一特点从题目中找到一点提示。

遇到的第一类题,是在矩阵中选出一些点,使这些点满足特定要求,然后计算方案数或者最优解。比如“放国王”、“方格棋盘”、“炮兵阵地”,这样的题一般是先处理出所有的单行合法状态,在对每一行分别进行判断,DP更新每行对应状态的解,最终结果就在最后一行的合法状态里面。

个人认为,比较坑的地方在计算顺序上,究竟是用当前行更新所有下一状态,还是用之前的状态来计算下一行,这个因题而异,但是目前遇到的多数题目都是前者(前者有种最短路里面的“松弛操作”的既视感)。

第二类题,就是给状压套上个面具,比如“旅游景点”是和SPFA联系起来,“愤怒的小鸟”是在精度还有特殊位置卡程序,“动物园”主要是处理环形的起始端比较麻烦,这样的题难点都不在于状态压缩上面,而是在处理合法状态上,在调程序的时候也是这部分的时间占了大头。

最后一类,就是很难看出来是怎么做的题。比如“学校食堂”、“集合选数”,这种题都是省选难度的,想半天也还是一点没思路,看了题解也一脸懵逼,考试很难(几乎不能)想到思路;还有“Bill的挑战”,在预处理的地方不太好想。对这种题,还是要锻炼一下脑洞,仔细想一想如何跟状压联系起来,然后再试一试自己猜的思路(虽然和正解差十万八千里。。。)。

嗯,状压DP主要就是这样,以后有时间还要回来把没干过去的题(集合选数、学校食堂)填填坑。

 

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974