题解 P3392 【涂国旗】

「已注销」 · 2018-08-09 12:57:49 · 题解

O(n^2+nm)

开数组w[i],b[i],r[i]，分别表示把前i行涂成白、蓝、红需要涂的格子数

设第1行到第i行是白色

第i+1行到第j行是蓝色

则第j+1行到第n行是红色

此时代价为w_i+b_j-b_i+r_n-r_j

枚举i,j，取最小值即可

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans=0x7fffffff,w[51],b[51],r[51];
string s;
inline int check(char c){
    int tot=0;
    for(int i=0;i<m;++i)
        if(s[i]!=c)++tot;
    return tot;    
}
int main(int argc, char const *argv[])
{
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>s;
        w[i]=w[i-1]+check('W');
        b[i]=b[i-1]+check('B');
        r[i]=r[i-1]+check('R');
    }
    for(int i=1;i<n-1;++i)
        for(int j=i+1;j<n;++j)
            ans=min(ans,w[i]+b[j]-b[i]+r[n]-r[j]);
    cout<<ans;        
    return 0;
}