GDOI2014 拯救莫莉斯 状压DP 动态规划

GDOI2014 拯救莫莉斯 状压DP

注意题目是“n*m<=50”,最坏情况应该是7x7的矩阵,显然不能直接暴搜,那么只能用状压DP来做。因为当前一行的状态选择只与其上下两行有关(第一行和最后一行例外),所以设f[i][j][k]表示前i行,i-1行状态为j,i行状态为k时的最优解。枚举行数、i-1行状态、i行状态、i+1行状态,···
状态压缩DP 小结 动态规划

状态压缩DP 小结

(题外话) 嗯,刚刚在调K,然后电脑挂了,程序运行居然关不掉,大概思路已经差不多了额,就先挖个坑,以后回家再调。。。   状压DP,主要就是把很难表示的DP过程中的状态压到一个int里,给这个数的每个二进制位赋予一个含义,感觉有点像以前DFS、回溯时候那个bool数组的作用。 状压的题数据···