状态压缩 dp 解决网格填充问题

· · 题解

其实，动规都是想明白后超简单 QaQ

相比楼上的题解没用啥优化，可能实现方法不大一样。

由典型的一道题：炮兵阵地 入手。这道题很显然可以设 f[i][j][k] 代表到 i 行为止，i 行状态是 j，i-1 行状态是 k，炮兵互不冲突大最大答案。这样的复杂度是枚举阶段的 n 乘状态 2^m*2^m 乘决策，即枚举上面前两行的状态，复杂度为 O((2^m)^3)。只是因为有每一行的合法状态很少（相邻两个一中间至少有两个零，大概 100 个），这样才把复杂度减少，从而通过这一题。

然而这一类问题有更普遍的一种解法，就是用更高的进制位（三进制）进行压缩，并存储更多的信息。我们规定放炮兵的位置为 2，2 的下面必须放 1，1 的下面必须放 0。0 的下面才可以任意放。这样我们内存可以省去一维，只用存当前第 i 行的状态

采用正向递推。考虑第 i+1 行填什么状态。需要满足：

  1. 第 i 行第 j 位为 2 时，第 i+1 行第 j 位填 1
  2. 第 i 行第 j 位为 1 时，第 i+1 行第 j 位填 0
  3. 山地不能填 2
  4. 一个格子填 2 后，右边两个格子不能填 2

因为转移比较复杂，不用写出转移方程，相邻两行进行 dfs 即可。

回到这题，我们将 2*3 和 3*2 的矩阵分别化为

2\quad 2 1\quad 1 0\quad 0

和

1\qquad 1 \qquad 1 0\qquad 0 \qquad 0

与炮兵阵地类似，采用正向递推，需要满足如下条件：

  1. 第 i 行第 j 位不为 0 且第 i+1 行第 j 位已损坏，转移失败
  2. 第 i 行第 j 位为 2 时，第 i+1 行第 j 位填 1
  3. 第 i 行第 j 位为 1 时，第 i+1 行第 j 位填 0
  4. 已损坏的格子填零跳过
  5. 可以尝试填上连续三个 1 或者连续两个 2

这样这道题就做完了，我做的时候，想过一个问题，就是何时累加答案，若在填连续两个 2 或者连续三个 1 的时候累加，那么最后一行填连续两个 2 显然是不合法的，芯片的下半部分就超出范围了。有两种解决办法，一种是判断一下边界条件，我采用的是另一种，正常做，只不过计算答案的时候直接用 f[n][0] 即可。

内存限制很小，滚动一下就行，改动不大。

放代码，注释很详细：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 155;
const int maxm = 11;
int a[maxn][maxm];
int T,n,m,k;
int f[2][60005];
int pow[11];
void init(){
    pow[0] = 1;
    for (int i = 1; i <= 10; i++) pow[i] = pow[i-1]*3;
}
int suan(int x, int pos){ // 数 x 的三进制第 pos 位是多少 
    return x%pow[pos]/pow[pos-1];
}
bool ifok(int x, int pos, int lst){ // 第 x 行第 pos 位是否能放 
    if (!a[x][pos] && !suan(lst,m-pos+1)) return 1; // 当前位置不能损坏，上一行当前位置必须为零 
    return 0; 
}
void dfs(int x/*这是第几行*/, int lst/*上一行的状态*/, int now/*当前行搜索到的状态*/,  int pos/*从左往右搜到第三进制几位*/, int cnt/*放了几个数了*/){
    if (!pos){ // 更新状态 
         f[x%2][now] = max(f[x%2][now],f[(x-1)%2][lst]+cnt);
         return;
    }
    if (suan(lst,pos)){//上一行当前非零 
        if (a[x][m-pos+1]) return;
        if (suan(lst,pos) == 2) dfs(x,lst,now*3+1,pos-1,cnt);
        else dfs(x,lst,now*3, pos-1,cnt); 
    } 
    else{
        dfs(x,lst,now*3,pos-1,cnt);//什么都不放，跳！ 
        if (pos >= 2 && ifok(x,m-pos+1,lst) && ifok(x,m-pos+2,lst)){ //尝试放 3*2 的 （竖的） 
            dfs(x,lst,(now*3+2)*3+2,pos-2,cnt+1); 
        } 
        if (pos >= 3 &&  ifok(x,m-pos+1,lst) && ifok(x,m-pos+2,lst) && ifok(x,m-pos+3,lst)){ //尝试放 2*3 的 （横的） 
            dfs(x,lst,((now*3+1)*3+1)*3+1,pos-3,cnt+1);
        }
    }
}
int main(){
    //freopen("a.in","r",stdin);
    init();
    cin >>T;

    while (T--){

        cin >> n >> m >> k;
        memset(a,0,sizeof a);
        for (int i = 1; i <= k; i++){
            int x,y;
            cin >> x >> y;
            a[x][y] = 1;
        }

        memset(f,-0x3f3f3f3f,sizeof f);
        f[0][0] = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < pow[m]; j++) f[(i+1)%2][j] = -0x3f3f3f3f;
            for (int j = 0; j < pow[m]; j++){
                if (f[i%2][j] < 0) continue;
                dfs(i+1,j,0,m,0);
            }
        }
        cout << f[n%2][0] << endl;
    }
    return 0;
}