P3392 涂国旗题解

题目

某国法律规定，只要一个由N×M个小方块组成的旗帜符合如下规则，就是合法的国旗。

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

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

小a很懒，希望涂最少的格子，使这块布成为一个合法的国旗。

输入输出格式

输入格式

第一行是两个整数N,M。

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

输出格式

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

输入输出样例

输入样例

4 5
WRWRW
BWRWB
WRWRW
RWBWR

输出样例

代码1

开数组w[i],b[i],r[i]，分别表示把前i行涂成白、蓝、红需要涂的格子数

设第1行到第i行是白色

第i+1行到第j行是蓝色

则第j+1行到第n行是红色

此时代价为wi+bj−bi+rn−rj，枚举i,j，取最小值即可。

#include
#include
using namespace std;
int n,m,ans=1000000000,w[51],b[51],r[51];
string s;
int check(char c){//改变的代价
	int tot=0;
	for(int i=0;i>n>>m;
	for(int i=1;i>s;
		w[i]=w[i-1]+check('W');//前面行的改变数加上这一行的改变数
		b[i]=b[i-1]+check('B');
		r[i]=r[i-1]+check('R');
	}
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n;j++){
			ans=min(ans,w[i]+b[j]-b[i]+r[n]-r[j]);//输入最小的代价
		}
	}
	cout< 
 代码2 
枚举白与蓝(a)、蓝与红的边界(b)，再统计三个区域里总共有多少格子需要涂改颜色，用一个变量来记录最优的答案（即需要涂改的格子数最少），不断更新，最后输出就OK了. 
#include
#include
using namespace std;
int n,m,mi=10000000;
char a[51][51];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j>a[i][j];//扫描进来现在的状态
		}
	}
	for(int i=1;i<=n-2;i++){//白与蓝的边界只到n-2，下面至少还有一行蓝色和一行红色
		for(int j=i+1;j<=n-1;j++){//蓝与红的边界只到n-1
			int ans=0;//每一次都清零，计算最小的
			for(int k=1;k<=i;k++){//边界以内都涂成白色
				for(int g=1;g<=m;g++){
					if(a[k][g]!='W'){
						ans++;
					}
				}
			}
			for(int k=i+1;k<=j;k++){
				for(int g=1;g<=m;g++){
					if(a[k][g]!='B'){
						ans++;
					}
				}
			}
			for(int k=j+1;k<=n;k++){
				for(int g=1;g<=m;g++){
					if(a[k][g]!='R'){
						ans++;
					}
				}
			}
			mi=min(ans,mi);
		}
	}
	cout<<mi;
	return 0;
}
                                                        本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/3508f53107.html

P3392 涂国旗题解

相关推荐