P3392 涂国旗

骑猪看日落 2023-02-17 03:12 3阅读 0赞

[题目][Link 1]  
某国法律规定，只要一个由 N \\times MN×M 个小方块组成的旗帜符合如下规则，就是合法的国旗。（毛熊：阿嚏——）

从最上方若干行（至少一行）的格子全部是白色的；  
接下来若干行（至少一行）的格子全部是蓝色的；  
剩下的行（至少一行）全部是红色的；  
现有一个棋盘状的布，分成了 NN 行 MM 列的格子，每个格子是白色蓝色红色之一，小 a 希望把这个布改成该国国旗，方法是在一些格子上涂颜料，盖住之前的颜色。

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

输入格式  
第一行是两个整数 N,MN,M。

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

输出格式  
一个整数，表示至少需要涂多少块。

输入输出样例  
输入 \#1复制  
4 5  
WRWRW  
BWRWB  
WRWRW  
RWBWR  
输出 \#1复制  
11  
说明/提示  
样例解释  
目标状态是：

WWWWW  
BBBBB  
RRRRR  
RRRRR  
一共需要改 11 个格子。

数据范围  
对于 100%100% 的数据，N,M \\leq 50N,M≤50。  
解题思路：枚举三个区域块的宽度即可。

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    int w[60],b[60],r[60];
    int  count_sum(int x,int y,int z)
    { 
    // cout<<x<<' '<<y<<' '<<z<<endl;
    	int i,j,k,sum=0;
    	for(i=1;i<=x;i++)//统计第一部分涂成白色 
    	sum=sum+b[i]+r[i];
    	for(j=x+1;j<=x+y;j++)//统计第二部分涂成蓝色 
    	sum=sum+w[j]+r[j];
    	for(k=x+y+1;k<=x+y+z;k++)//统计第三部分涂成红色 
    	sum=sum+w[k]+b[k];
    	return sum;
    }
    int main()
    { 
       ios::sync_with_stdio(0),cin.tie(0);
       int n,m,i,j,k,minv=1e5;
       char c;
       cin>>n>>m;
       for(i=1;i<=n;i++)//统计每行中白蓝红各有多少个格子 
       for(j=1;j<=m;j++)
       { 
       	cin>>c;
       	if(c=='W')
       	w[i]++;
       	else if(c=='B')
       	b[i]++;
       	else
       	r[i]++;
       }
    // for(i=1;i<=n;i++)
    // cout<<w[i]<<' '<<b[i]<<' '<<r[i]<<endl;
       for(i=1;i<=n-2;i++)//白色格子从1行枚举到n-2行
       for(j=1;j<=n-i-1;j++)//蓝色格子在剩下的n-i行里面枚举，但是至少要空出一行给红色格子
       { 
       	k=n-i-j;//红色格子的行数
       	minv=min(minv,count_sum(i,j,k));//之前与count函数命名重复，出现错误 
       } 
       cout<<minv;
       return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P3392