1.每一行用一个二进制数表示, 有些二进制数是题目中不合法的状态,我们可以预处理出一行合法状态,放在一个数组里面,在递推的过程中复杂度就会大大降低。
POJ 3254 Corn Fields 解题报告
POJ 3311 Hie with the Pie code
HDU 4539 郑厂长系列故事――排兵布阵 code
POJ 1185 炮兵阵地 code
2.MST问题,dp[i][j]表示到点j时各个点访问的状态为i时的最值。
HDU 3001 Travelling code
POJ 2288 Islands and Bridges code
3.与第二个差不多,但有点区别,可以自己YY
ZOJ 3471 Most Powerful code
4.贴砖块类问题.(可以参考第二题的报告)
POJ 2411 Mondriaan's Dream code
SGU 131 Hardwood floor code
POJ 1038
Bugs Integrated, Inc. code
5.综合题,状态压缩+矩阵乘法+高精度(除以2, 减1)
SGU 197 Nice Patterns Strike Back code