Description：
给你一个n * m的方格纸，有一些格子无法被覆盖，然后用2*3的格子覆盖这个方格纸，问你最多能放多少个格子
神级状压
为了弄清楚这道题翻了无数篇解题报告，最后终于搞明白了
用三进制表示每行的状态。
比如对于第i行第j列的格子，如果i-1行，i行的j列都是空的则用0表示，i行的j列不能放用2表示，剩下的（仅i - 1行的j列不能放）用1表示
然后深搜进行转移
干讲没意思，具体看注释，写的很清楚了（AC代码是poj的，稍微改一下输入输出就是洛谷的、
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int N = 59050; /*pre表示你枚举的上一个状态，now表示你现在枚举的状态*/ int dp[2][N], mp[160][15], pre[12], now[12], n, m, d, cur; int base[] = {0,1,3,9,27,81,243,729,2187,6561,19683,59049}; void init(){ memset(mp, 0, sizeof(mp)); memset(dp, -1, sizeof(dp)); } /*3进制转10进制*/ int trans(int *t){ int ans = 0; for(int i = 1; i <= m; i++) ans += t[i] * base[i]; return ans; } /*10进制转3进制*/ void chan(int t, int *p){ for(int i = 1; i <= m; i++) p[i] = t % 3, t /= 3; return ; } /*i为当前行，j为当前状态，cnt为格子数目，tmp为当前压缩后整行状态*/ void dfs(int i, int j, int cnt, int tmp){ int k; dp[i & 1][tmp] = max(dp[i & 1][tmp], cnt); if(j >= m) return ; /*放上3行2列的格子 如果该层状态和前一层的状态都允许 也就是都能放格子 那么就放上格子继续搜下去*/ if(!pre[j] && !pre[j + 1] && !now[j] && !now[j + 1]){ now[j] = now[j + 1] = 2; //放格子之后状态就都是2了 k = trans(now); dfs(i, j + 2, cnt + 1, k);//因为两格都被覆盖，跳过去搜 now[j] = now[j + 1] = 0; //回溯 } /*放上2行3列的格子 这个就只跟你当前的状态 也就是i行j列和i-1行j列是否为空 而这一信息仅存储在now[j]上 j+1列 j+2列同理*/ if(j < m - 1 && !now[j] && !now[j + 1] && !now[j + 2]){ now[j] = now[j + 1] = now[j + 2] = 2; //同样修改 搜下去 回溯 k = trans(now); dfs(i, j + 3, cnt + 1, k); now[j] = now[j + 1] = now[j + 2] = 0; } dfs(i, j + 1, cnt, tmp); return ; } int main(){ int T, x, y; scanf("%d", &T); while(T--){ init(); scanf("%d%d%d", &n, &m, &d); for(int i = 1; i <= d; i++){ scanf("%d%d", &x, &y); mp[x][y] = 1; } for(int i = 1; i <= m; i++) pre[i] = 2; int tmp = trans(pre); dp[0][tmp] = 0; //对于第0行来说，只有啥都不能放这一种状态 将该状态价值为0 for(int i = 1; i <= n; i++){ memset(dp[i & 1], -1, sizeof(dp[i & 1])); //初始化本次要用的dp数组 for(int j = 0; j < base[m + 1]; j++){ //枚举上一行的状态 /* 如果上一行的状态dp数组为-1，说明上一层的该状态根本达不到，那么就不能用来转移*/ if(dp[i + 1 & 1][j] == -1) continue; chan(j, pre); //将上一层的状态转换成3进制 for(int k = 1; k <= m; k++) if(mp[i][k]) now[k] = 2; //如果此时第k位无法覆盖，那么就为状态为2 /*不然，上层2状态变为1状态，其余为0(根据状态的定义就可以得出)*/ else now[k] = max(pre[k] - 1, 0); cur = dp[i + 1 & 1][j]; //cur表示上一层该状态达到的最大价值 dfs(i, 1, cur, trans(now)); //dfs转移 因为第一格前为第0格不能放，所以状态为1 } } int ans = 0; for(int i = 0; i < base[m + 1]; i++) ans = max(ans, dp[n & 1][i]); printf("%d ", ans); } return 0; }
用这种多进制表示然后dfs转移的方法可以做出绝大多数的状压题，尤其是状态表示较复杂（一般需要表示两个及以上状态的），转移方程不好写而冗余状态较多的题
比如炮兵阵地，也可以用三进制表示状态然后dfs转移。但是由于炮兵阵地的总状态数并不多，所以可以直接枚举子集，写起来更省力。