ABC283E状态压缩暴力枚举动态规划

暴力枚举当前两行（i和i-1行）是否发生改变，记录前i-1行合法的最小次数。最后一行特判一下。

#include <bits/stdc++.h>
#define N 1005
using namespace std;
int n, m, i, j, k, a[N][N], f[N][9];
int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};
int bad(int k, int o, int p, int q){
    int i=k-1, j, x, y, z, s[]={q, o, p, p};
    for(j=1; j<=m; j++){
        for(k=0; k<4; k++){
            x = i+dx[k], y = j+dy[k], z = s[k];
            if((a[i][j]^p^a[x][y]^z) == 0) k = 9;
        }
        if(k < 9) return N;//该数字周围均不相同，返回无穷大
    }
    return 0;//正常返回0，可加
}//第k行状态为o，上一行为p，再上一行为q，第k-1行是否合法
int main(){
    scanf("%d%d", &n, &m);
    memset(a, 9, sizeof(a));//边界无穷大定不相同
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            scanf("%d", &a[i][j]);
        }
    }
    memset(f, 9, sizeof(f));
    for(j=0; j<4; j++) f[2][j] = j/2 + j%2 + bad(2, j/2, j%2, 0);//第二行赋初值
    for(i=3; i<=n; i++){
        for(j=0; j<4; j++){//当前行状态为j/2，上一行为j%2
            for(k=0; k<4; k++){//上一行做题为k/2，再上一行为k%2
                if((j&1) != (k>>1)) continue;//接不上矛盾
                if(bad(i, j>>1, j&1, k&1)) continue;//不能保证第i-1行合法，后面无法挽回无解
                f[i][j] = min(f[i][j], f[i-1][k]+(j>>1));//前i-1行用了f[i-1][k]次，当前行用了j/2次
            }
        }
    }
    for(k=N, j=0; j<4; j++){
        k = min(k, f[n][j]+bad(n+1, 0, j/2, j%2));
    }//最后一行状态为j，看一下是否合法
    printf("%d\n", k>n?-1:k);
    return 0;
}

写法2：状态不压缩也行。容易想到f[i]表示前i行没问题的最少操作次数，但第i行还会受到下一行影响，所以我们只需要保证前i-1行没问题就行。在枚举下一行的时候，我们需要知道上一行的状态，所以还需要记录上一行是否变换。这样，状态f[i][x][y]就出来了，表示前i-1行没问题，第i行和i-1行状态分别是x、y的最优值。

#include <bits/stdc++.h>
#define N 1005
using namespace std;
int n, m, i, j, k, t, x, y, z, ans=N, a[N][N], f[N][2][2];
int ok(int k){
    if(k < 1) return 1;
    for(j=1; j<=m; j++){
        t = a[k][j] ^ y;//该元素周围都跟他不一样，不合法。
        if(t!=(a[k][j-1]^y) && t!=(a[k][j+1]^y) && t!=(a[k-1][j]^z) && t!=(a[k+1][j]^x)) return 0;
    }
    return 1;
}
int main(){
    scanf("%d%d", &n, &m);
    memset(a, 9, sizeof(a));
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++) scanf("%d", &a[i][j]); 
    }
    memset(f, 9, sizeof(f));
    f[0][0][0] = 0;
    for(i=1; i<=n+1; i++){//枚举到n+1，保证前n行没问题
        for(x=0; x<=1; x++){//i
            for(y=0; y<=1; y++){//i-1 
                for(z=0; z<=1; z++){//i-2
                    if(!ok(i-1)) continue;//不能保证i-1行没问题
                    f[i][x][y] = min(f[i][x][y], f[i-1][y][z] + x);//取之前最小值，加上当前是否操作
                }
                if(i > n) ans = min(ans, f[i][x][y]);
            }
        }
    }
    if(ans > n) ans = -1;
    printf("%d\n", ans);
    return 0;
}