P3392 涂条纹

题目描述

只要一个由 个小方块组成的旗帜符合如下规则，就是合法的图案。

• 从最上方若干行（至少一行）的格子全部是白色的；
• 接下来若干行（至少一行）的格子全部是蓝色的；
• 剩下的行（至少一行）全部是红色的；

现有一个棋盘状的布，分成了 行 列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成合法图案，方法是在一些格子上涂颜料，盖住之前的颜色。

小 A 很懒，希望涂最少的格子，使这块布成为一个合法的图案。

输入格式

第一行是两个整数 。

接下来 行是一个矩阵，矩阵的每一个小方块是 W（白），B（蓝），R（红）中的一个。

输出格式

一个整数，表示至少需要涂多少块。

输入输出样例 #1

输入 #1

4 5
WRWRW
BWRWB
WRWRW
RWBWR

输出 #1

11

说明/提示

样例解释

目标状态是：

WWWWW
BBBBB
RRRRR
RRRRR

一共需要改 个格子。

数据范围

对于 的数据，。

思路：1，暴力枚举:

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;
	if(!(cin>>n>>m)) return 0;
	vector<string>grid(n);
	for(int i=0;i<n;i++) cin>>grid[i];
	int min_cost=2500;
	//i表示白色区域的最后一行(注意下标凑从0开始，所以最大是n-3
	for(int i=0;i<=n-3;i++){
		//j表示蓝色区域的最后一行，因为必须再白色下面，所以从i+1开始
		//至少给红色留一行，所以j最大为n-2
		for(int j=i+1;j<=n-2;j++){
			int current_cost=0;
			//1,计算把0-i行全染成白色的代价
			for(int r=0;r<=i;r++){
				for(int c=0;c<m;c++){
					if(grid[r][c]!='W') current_cost++;
				}
			} 
			//计算从i+1到j行全染成b
			for(int k=i+1;k<=j;k++){
				for(int d=0;d<m;d++){
					if(grid[k][d]!='B') current_cost++;
				}
			} 
			//计算把从j+1行到第n-1行全染成红色的代价
			for(int p=j+1;p<=n-1;p++){
				for(int o=0;o<m;o++){
					if(grid[p][o]!='R') current_cost++;
				}
			}
			min_cost=min(min_cost,current_cost); 
		} 
	}
	cout<<min_cost<<endl; 
}

思路2：前缀和优化:

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main(){
	//为了让前缀和的计算更加自然，我们让数组的下标从1开始 
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;
	if(!(cin>>n>>m)) return 0;
	vector<string>grid(n+1);
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		grid[i]=" "+s;//在字符串前面补一个空格。让真实的下标u而从1开始 
	}
	//prefW[i] 表示前i行全变成白色的代价，默认 初始化为0
	vector<int>preW(n+1,0);
	vector<int>preB(n+1,0);
	vector<int>preR(n+1,0);
	//1,预处理前缀和数组
	for(int i=1;i<=n;i++){
		int costW=0,costB=0,costR=0;
		//统计当前第i行变成W,R,B分别要改几个格子
		for(int j=1;j<=m;j++){
			if(grid[i][j]!='W') costW++;
			if (grid[i][j] != 'B') costB++;
			if (grid[i][j] != 'R') costR++;
		} 
		//把当前的第i行的结果累加到前缀和数组中 
		preW[i]=preW[i-1]+costW;
		preB[i]=preB[i-1] + costB;
		preR[i]=preR[i-1] + costR;
	} 
	int min_cost=n*m;//最大的代价不可能超过格子的总数
	//2.枚举分界线i和j，i从1开始到n-2
	for(int i=1;i<=n-2;i++){
		for(int j=i+1;j<=n-1;j++){
			int current_cost=preW[i]+preB[j]-preB[i]+preR[n]-preR[j];
			min_cost=min(min_cost,current_cost);
		}
	} 
	cout<<min_cost<<endl;
	return 0;
}

知识补充:https://gemini.google.com/app/e8f3b17bcc27a3f0?pli=1

喜欢的话就赞一下吧