首页 > 代码库 > 涂国旗
涂国旗
【题目描述】
某国法律规定，一个由N*M(N,M <= 50)个小方块组成的合法旗帜应符合以下规则：
(1)从最上方开始，连续若干行( >= 1)的格子全部是白色的；
(2)接下来连续的若干行( >= 1)的格子全部是蓝色的；
(3)剩下的若干行( >= 1)的格子全部是红色的。
现有一块棋盘状的布料，分成了N*M的格子，每个格子是白色、蓝色、红色三种颜色的其中之一，在这块布料的一些格子上涂抹颜料，盖住之前的颜色，从而改成合法旗帜，询问至少涂多少格子。
【输入描述】
第一行输入两个整数N、M；
接下来N行输入一个矩阵，矩阵的每一格为‘W‘（白）、‘B‘（蓝）、‘R‘（红）中的一个。
【输出描述】
输出一个整数，表示至少需要涂多少块。
【输入样例】
4 5
WRWRW
BWRWB
WRWRW
RWBWR
【输出样例】
11
【数据范围及提示】
样例的目标状态是：
WWWWW
BBBBB
RRRRR
RRRRR
至少需要改11个格子。
源代码：#include<iostream>#define INF 1000000000using namespace std;int m,n,ans=INF,i[50][3]={0},Sum[50][3]={0};int main(){ cin>>n>>m; for (int a=1;a<=n;a++) //读入很恶心，豁出去了。 { for (int b=1;b<=m;b++) { char t; cin>>t; if (t==‘W‘) { i[a][1]++; i[a][2]++; } if (t==‘B‘) { i[a][0]++; i[a][2]++; } if (t==‘R‘) { i[a][0]++; i[a][1]++; } } Sum[a][0]+=Sum[a-1][0]+i[a][0]; //还是不冷静。 Sum[a][1]+=Sum[a-1][1]+i[a][1]; Sum[a][2]+=Sum[a-1][2]+i[a][2]; } for (int a=2;a<n-1;a++) for (int b=a+1;b<n;b++) ans=min(ans,Sum[a-1][0]+Sum[b-1][1]-Sum[a-1][1]+Sum[n][2]-Sum[b-1][2]); cout<<ans; return 0;}/* 解题思路： 看到题目中那小小的数据范围，不禁颓于暴力的毒瘾之中。 可以对暴力O(n^4)进行优化，利用前缀和来求区间修改数，便可以将O(n^2)转化为O(1)。*/
涂国旗
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。