P9653 『GROI-R2』 不空白的画布

· · 题解

贪心。

约定：

对于一组连续两个颜色都相同的格子，在下文中将被称作双连。

对于一组连续两个的格子，在下文中将被称作连双。

对于一组连续三个颜色都相同的格子，在下文中将被称作三连。

对于一组连续三个的格子，在下文中将被称作连三。

思路：

观察 k 的取值，我们会发现 k 至少为 3。这就说明，我们完全可以保证改动后的格子与两边不同色。那么，k 的存在就没有多少意义了，只需要标记出哪些格子需要变色即可。

初始时先统计出未修改时的答案，再进行贪心的修改，让答案最大化。

显然的，对于一个三连，我们可以通过改变中间格子，而使答案块数加上 2。而对于双连，我们改变其中任意一个格子，收益都只为 1。

所以我们先枚举每一个连三，判断是否是三连，是则变中间格，不是略过，然后再枚举连双进行判断并依据判断结果进行改变即可。

这样显然能够最大化 m 次修改所带来的收益。

代码：

#include<bits/stdc++.h>
using namespace std;
int jsq=-1;//修改赋特殊值保证不同不可能被判定成双/三连
int main(){
    int t;cin>>t;
    while(t--){
        int n,m,k;cin>>n>>m>>k;
        int c[500005]={},ans=0;
        for(int i=1,flag=(--jsq);i<=n;i++){
            cin>>c[i];
            if(flag!=c[i]) ans++,flag=c[i];//初始统计答案
        }
        for(int i=2;m&&i<n;i++) if(c[i-1]==c[i]&&c[i]==c[i+1]) m--,c[i]=(--jsq),ans+=2;//枚举连三判断三连
        for(int i=1;m&&i<n;i++) if(c[i]==c[i+1]) m--,c[i]=(--jsq),ans++;//枚举连双判断双连
        cout<<ans<<endl;
    }
    return 0;
}