1.每一行用一个二进制数表示, 有些二进制数是题目中不合法的状态,我们可以预处理出一行合法状态的个数,在递推的过程中复杂度就会大大降低。
POJ 3254 Corn Fields code
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