56分的,求助大佬们............
  • 板块P3392 涂国旗
  • 楼主456laji
  • 当前回复8
  • 已保存回复8
  • 发布时间2020/5/14 23:45
  • 上次更新2023/11/7 02:27:07
查看原帖
56分的,求助大佬们............
312780
456laji楼主2020/5/14 23:45

代码丑陋,见谅。

思路:

用双重for循环,求出三个区域的范围大小。

用前缀和,求出这个三个区域中B ,W,R这三个的值。

最后找出最大值。用n*m减去这个最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=500;
const int INF=0x7f7f7f;
char mp[N][N],w[N],r[N],b[N];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++){
		w[i]=w[i-1];r[i]=r[i-1];b[i]=b[i-1];
		for(int j=1;j<=m;j++)
		{
			char a;
			cin>>a;
			if(a=='W') w[i]++;
			if(a=='R') r[i]++;
			if(a=='B') b[i]++;
		}
	}
	
	long long a,c,z,cnt=0;
	long long  res=0;
	for(int i=n-2;i>=1;i--)
	{
		a=(w[i]-w[0]);
		for(int j=n-1;j>i;j--)
		{
			c=(b[j]-b[i]);
			z=(r[n]-r[j]);
			cnt=z+c+a;
			res=max(cnt,res);	
		}
	}
	printf("%lld\n",(n*m)-res);
	return 0;
}
2020/5/14 23:45
加载中...