牛客周赛 Round 32 F.小红的矩阵修改【三进制状态压缩dp】

原题链接：https://ac.nowcoder.com/acm/contest/75174/F

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小红拿到了一个字符矩阵，矩阵中仅包含"red"这三种字符。

小红每次操作可以将任意字符修改为"red"这三种字符中的一种。她希望最终任意两个相邻的字母都不相同。小红想知道，至少需要修改多少个字符？

输入描述:

第一行输入两个正整数n,m，代表矩阵的行数和列数。
接下来的n行，每行输入一个长度为m的、仅由"red"这三种字符组成的字符串。
1≤n≤4
1≤m≤1000

输出描述:

一个整数，代表需要修改的字母数量的最小值。

示例1

输入

2 3
ree
dee

输出

2

说明

修改为：
red
dre
即可。

解题思路：

我看到这个题目的时候直接就想到了线性dp，直接设f[i][j][0]表示当前位置为'r'，f[i][j][1]表示当前位置为'e'，f[i][j][1]表示当前位置为'd'，时最少的修改次数，可以保证让当前位置和左边和上边都不同，但是我忽略掉了一个问题，就是这样只能保证当前位置所在行和所在列合法，左上角其他部分不一定合法，如下如所示，所以这样dp是不对的，如下图所示：

也就是说我们只能保证当前所在行蓝色部分和当前所在列红色部分合法，但是左上角红色和蓝色相交部分，也就是绿色部分不一定合法，例如当[i,j]为r，[i,j-1]为d，[i-1,j]为e，此时的[i-1][j-1]如果为d那么对于[i-1,j]合法，但是会导致[i,j-1]不合法了，此时的[i-1,j-1]如果为e那么对于[i,j-1]合法，但是会导致[i-1,j]不合法，所以说这种dp方式是错误的。

这个题目正解是状态压缩dp,下面考虑状态压缩dp，但是这个题目还有一点特殊的地方，就是常规的状态压缩dp是以列来压缩状态，但是这里的列m非常大，所以不能以列来压缩状态，但是我们可以发现行非常小，我们可以以行来压缩状态，假设有n行，常规情况下是有(1<<n)种状态，但是这里每个位应该有三种状态，所以这里不像常规的状态压缩dp，常规的状态压缩都是二进制压缩，但是这个题目需要三进制压缩，所以有3^n中状态，然后按照二进制压缩dp的模式稍微改一改就行，改成三进制压缩就行了，其他部分都是一样的。

状态压缩dp处理如下：

我们先预处理所有合法状态，然后再考虑状态转移。

状态定义：

定义f[i][j]表示处理完前i列，并且第i列状态为j的最少修改次数。

状态转移：

当前行必须保证任意相邻位置不相同，当前行由前一行转移过来。

a表示当前行变为的状态，b表示前一行的状态，v1表示当前行变为状态a的修改次数

f[i][a]=min(f[i][a],f[i-1][b]+v1)

最终答案：

最终答案肯定是处理完前m-1行，最后一行的状态为某一个合法状态的最小值，j表示某一个合法状态

min(f[m-1][j])

时间复杂度：这个时间复杂度不太好表示，那么就粗略估计一下吧，大概是O(m*(state^2))，state表示合法状态数。

空间复杂度：空间大概为O(m*(3^n))，n表示行数，m表示列数。

cpp代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N=6,M=1010;
int n,m;
char gg[N][M];
int g[N][M];    //映射数组，将原来的red映射为012
vector<int>state;  //存储所有合法状态
vector<int>arrive[100]; //存储每个合法状态的所有合法转移
int p3[5]={1,3,9,27,81}; //存储3的幂
int f[M][100]; //f[i][j]表示处理完前i行，并且第i行状态为j的最少修改次数

bool check(int x)  //检查当前状态x是否合法，合法指的是x的三进制表示所有相邻位都不相同
{
    int last=-1,cnt=n;
    while(cnt--){
        int v=x%3;
        if(v==last)return false;
        x/=3;
        last=v;
    }
    return true;
}

bool check(int x,int y) //判断俩个数的三进制表示是否所有位都不同，
{
    for(int i=0;i<n;i++){
        if(x%3==y%3)return false;
        x/=3,y/=3;
    }
    return true;
}
int a1[4]={};
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)scanf("%s",gg[i]);
    for(int i=0;i<n;i++)//先把red映射为012
        for(int j=0;j<m;j++)
            if(gg[i][j]=='r')g[i][j]=0;
            else if(gg[i][j]=='e')g[i][j]=1;
            else g[i][j]=2;
    for(int i=0;i<p3[n];i++) //首先预处理所有合法状态
    {
        if(check(i))state.push_back(i);
    }
    
    for(int i=0;i<state.size();i++){ //预处理每个合法状态的所有合法转移
        
        for(int j=0;j<state.size();j++)
        {
            //当俩行三进制表示每个位都不同时，才能转移
            if(check(state[i],state[j]))arrive[i].push_back(j);
        }
    }
    memset(f,0x3f,sizeof f);
    for(int i=0;i<m;i++)
    {
        for(int a=0;a<state.size();a++){
            for(int j=0;j<n;j++)a1[j]=0;  //记得a1数组要初始化，不初始化可能会受到前面的影响
            int x=state[a],v1=0,cnt1=0;
            while(x){
                a1[cnt1++]=x%3;
                x/=3;
            }
            for(int j=0;j<n;j++)
                if(g[j][i]!=a1[j])v1++; //计算当前位置变为状态state[a]需要修改多少次
            if(i==0){
                f[i][a]=v1; //第一行前面没有行，所以特殊处理，
                continue;
            }
            for(auto b:arrive[a]){  //前面预处理好了所有合法转移，所以这里直接计算即可
                f[i][a]=min(f[i][a],f[i-1][b]+v1);
            }
        }
    }
    int ans=0x3f3f3f3f;
    //计算答案，非法状态会是一个非常大的值，所以这里我们直接枚举所有状态也不影响答案
    for(int j=0;j<p3[n];j++)
        ans=min(ans,f[m-1][j]);
    cout<<ans<<endl;
    return 0;
}