首页 > 代码库 > 洛谷P3392 涂国旗

洛谷P3392 涂国旗

2024-08-14 21:24:53   220人阅读

 

题目描述

某国法律规定，只要一个由N*M个小方块组成的旗帜符合如下规则，就是合法的国旗。（毛熊：阿嚏——）

  • 从最上方若干行（>=1）的格子全部是白色的。

  • 接下来若干行（>=1）的格子全部是蓝色的

  • 剩下的行（>=1）全部是红色的

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

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

输入输出格式

输入格式：

 

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

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1：
4 5WRWRWBWRWBWRWRWRWBWR
输出样例#1：
11

说明

样例解释：

目标状态是

WWWWWBBBBBRRRRRRRRRR

一共需要改11个格子

对于100%的数据，N，M<=50

 

先算一下把各行涂成各个颜色要涂的格子数（可以用前缀和优化），然后动规，枚举颜色分界线，找最优解。

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}11     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}12     return x*f;13 }14 const int mxn=60;15 int mp[mxn][mxn];16 int c[mxn][5];//前[i]行颜色x的个数 17 int n,m;18 int main(){19     n=read();m=read();20     int ans=1e5;21     int i,j;22     char s[mxn];23     for(i=1;i<=n;i++){24         scanf("%s",s+1);25         for(j=1;j<=m;j++){26             if(s[j]==‘W‘)c[i][1]++;27             if(s[j]==‘B‘)c[i][2]++;28             if(s[j]==‘R‘)c[i][3]++;29         }30         for(j=1;j<=3;j++)c[i][j]+=c[i-1][j];31     }32     for(i=1;i<=n-2;i++){33         for(j=i+1;j<n;j++){34             int numW=i*m-c[i][1];//涂白色数量 35             int numB=(j-i)*m-(c[j][2]-c[i][2]);36             int numC=(n-j)*m-(c[n][3]-c[j][3]);37             ans=min(ans,numW+numB+numC);38         }39     }40     cout<<ans<<endl;41     return 0;42 }

 

洛谷P3392 涂国旗


联系
我们