题解 | #小红的矩阵染色#

void solve(){
    int n,m,k;cin>>n>>m>>k;
    vector<string> g(n);
    for(int i=0;i<n;i++) cin>>g[i];
    vector<int> seqs;
    for(int i=0;i<m;i++){
        int curr=0;
        for(int j=0;j<n;j++){
            if(g[j][i]=='o') curr++;
            else{
                if(curr>=2) seqs.pb(curr);
                curr=0;
            }
        }
        if(curr>=2) seqs.pb(curr);
    }
    sort(seqs.rbegin(),seqs.rend());
    // VOUT(seqs,0,seqs.size());
    int ans=0;
    for(int val:seqs){
        if(val>=2){
            if(k>=val)
                ans+=val-1,k-=val;
            else if(k>=2){
                ans+=k-1;k=0;break;
            }
        }
        if(k==0) break;
    }
    cout<<ans<<'\n';
}

int main()
{
    int t=1;
	// cin>>t;
	while(t--)solve();
}

1. 对一个长度 的竖直白色格子区域，可以染色，得分 ，即损失一个格子的分数。
2. 因此格子区域长度越大，分数损失越少，优先选择长度最大的竖直白色格子区域染色。
3. 如果 不大于1，染色不再增加分数，可以退出，否则遍历所有区域，直到区域用尽或者某个区域满足 ， 则染色这个区域的前 个格子然后退出（不然会WA20）