本文主要是介绍poj 1038 - Bugs Integrated, Inc.(状态压缩dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
从n*m的矩阵中裁剪2*3的小矩形，其中有些方块不能用【题目以坐标方式给出】，问最多可以得到多少小矩形。
思路：
要知道能否以当前行作为小矩形的最后一行，需要知道以上三行的状态信息，因为我们切割的时候可以横着也可以竖着。
同时由于一旦 方格 （x-1, y）被黑色记号或其他芯片占据，则方格（x-2,y）即便空闲对第 x行芯片的放置也毫无意义，所以每个节点用3个状态就可以表示,
状态压缩压两行
用3进制表示0表示都没有
1表示第x-1行有
2表示第x行有
代码如下：
const int tri[15] = {0, 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};
int n, m, k, dp[2][59049], pre[15], now[15]; //滚动数组来记录
bool g[155][15];
int getTen(int *a)//把一个用数组表示的状态转化为一个10进制整数
{int ans = 0;for(int i = 1; i <= m; ++i)ans += a[i]*tri[i];return ans;
}
void getTri(int v, int *a)//把一个整数转化为一个数组来表示状态
{for(int i = 1; i <= m; ++i) {a[i] = v%3;v /= 3;}
}
void dfs(int x, int y, int last, int key)
{int k;dp[x&1][key] = max(dp[x&1][key], last);if(y >= m) return;if(!pre[y] && !pre[y+1] && !now[y] && !now[y+1]) {//竖着切割now[y] = now[y+1] = 2;k = getTen(now);dfs(x, y+2, last+1, k);now[y] = now[y+1] = 0;}if(y<m-1 && !now[y] && !now[y+1] && !now[y+2]) { //横着切割now[y] = now[y+1] = now[y+2] = 2;k = getTen(now);dfs(x, y+3, last+1, k);now[y] = now[y+1] = now[y+2] = 0;}dfs(x, y+1, last, key); //不做改动，直接下一行
}
int main()
{int t, a, b, tmp;scanf("%d", &t);while(t--) {scanf("%d%d%d", &n, &m, &k);memset(g, 0, sizeof(g));for(int i = 0; i < tri[m+1]; ++i) dp[1][i] = -1;for(int i = 0; i < k; ++i) {scanf("%d%d", &a, &b);g[a][b] = 1;}for(int i = 1; i <= m; ++i)pre[i] = g[1][i]+1; //设置第一行的状态，第0行的方块全部视为不可用tmp = getTen(pre);dp[1][tmp] = 0;for(int i = 2; i <= n; ++i) {for(int j = 0; j < tri[m+1]; ++j) dp[i&1][j] = -1;for(int j = 0; j < tri[m+1]; ++j) {if(dp[(i+1)&1][j] == -1) continue; //跳过不可能的子状态getTri(j, pre);for(int l = 1; l <= m; ++l) //根据上一行的状态得到本行的状态if(g[i][l]) now[l] = 2;else now[l] = max(pre[l]-1, 0);tmp = getTen(now);dfs(i, 1, dp[(i+1)&1][j], tmp);}}int ans = 0;for(int i = 0; i < tri[m+1]; ++i)ans = max(ans, dp[n&1][i]);printf("%d\n", ans);}return 0;
}
这篇关于poj 1038 - Bugs Integrated, Inc.(状态压缩dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
