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

洛谷P3392 涂国旗

 

题目描述

某国法律规定,只要一个由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 涂国旗