本文主要是介绍牛客周赛 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映射为012for(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;
}这篇关于牛客周赛 Round 32 F.小红的矩阵修改【三进制状态压缩dp】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
