题解：AT_pakencamp_2019_day3_d パ研軍旗

题意简述

给定 \(5\) 行 \(N\) 列的网格，每个格子有四种可能的颜色。

要使网格中每一列的颜色都一样但不能是黑色，并且相邻两列的颜色不相同。问最少改变多少个格子的颜色能满足要求。

思路分析

为方便处理，把给定的红色、蓝色、白色、黑色分别转成数字 \(1,2,3,4\)。

考虑 dp。

不妨设 \(c_{i,j}\) 为将第 \(i\) 列全部变成第 \(j\) 种颜色的代价，\(f_{i,j}\) 表示第 \(i\) 列变成第 \(j\) 种颜色时前 \(i\) 列的总代价。

那么思路就很简单了。对于当前列的当前颜色，其总代价应为前一列不同颜色的总代价的最小值与将当前列转变为当前颜色的代价的和，即状态转移方程为 \(f_{i,j}=\min(f_{i-1,k})+c_{i,j}(j \ne k)\)，最后在最后一列的几种颜色中取最小值即可。

细节内容见代码注释。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005;
int n,ans=0x3f3f3f3f,mp[10][N],c[N][5],f[N][5];//mp表示原矩阵，c和f如上文 
//将字符转为数字 
int change(char ch){
	switch(ch){
		case 'R':return 1;break;
		case 'B':return 2;break;
		case 'W':return 3;break;
		case '#':return 4;break;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=5;++i)
		for(int j=1;j<=n;++j){
			char ch;cin>>ch;
			mp[i][j]=change(ch);
		}
	//预处理代价 
	for(int i=1;i<=n;++i)//枚举列 
		for(int j=1;j<=3;++j)//枚举颜色，因为不能是黑色，所以只枚举三种 
			for(int k=1;k<=5;++k){
				if(mp[k][i]==j)continue;
				++c[i][j];
			}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=3;++j){
			f[i][j]=0x3f3f3f3f;
			for(int k=1;k<=3;++k){
				if(j==k)continue;//相邻两列颜色不能一样 
				f[i][j]=min(f[i][j],f[i-1][k]+c[i][j]);//状态转移 
			}
		}
	}
	//在最后一列的几种颜色中取最小值 
	for(int i=1;i<=3;++i)ans=min(ans,f[n][i]);
	cout<<ans;
	return 0;
}

时间复杂度分析

用 \(N\) 表示网格列数，\(M\) 表示网格行数，\(K\) 表示颜色数量，则预处理的时间复杂度为 \(O(NMK)\)，dp 时间复杂度为 \(O(NK^{2})\)。本题中 \(M\) 和 \(K\) 都为常数，故时间复杂度较低，通过此题没有任何问题。