Problem

Solve

先不看yy，我们能够发现这个youyou可以贪心，即：
某一列全是1，全选，有一个1，尽量只选1(因为可能和上一列的选择连不起来，要衔接)，全0，尽量不要选
再回来看yy,通过题意以及样例等数据来看，我们能够发现这个yy肯定只会对满足这样的列进行操作：
上下两行只选了一行1，另一行是0
通过手玩得知，不看yy的方案似乎真的可以成为一种策略，但是要被yy减去一些
然后还有一种方案(样例#1及编造)是刻意抵抗yy,直接让能换的列全选，虽然多了0，但是比yy的多了0还少了1要好多了
不难发现，除了以上两种方案，其余的方案都是劣的，证明:

假设选择第一个方案，中间不改动，且yy没来时结果为X
则yy来了是结果为X-2m(如果能用完更换次数的话)
那此时我做一些改动(结合第二个方案)，结果一定会<X-2m
则yy来了是结果为X-2y(如果用不完，y是更换的次数)
做一些改动会使得结果变大，因为有些列阻止yy换了，及时止损
那此时我们直接使用方案2获得最大收益

那问题就简单了，对于方案2，直接DP求每列收益的最大子段和，答案记作\(a\)
对于方案1，我们这里也采取DP的方式:
设\(f_{i,0/1,0/1}\)为第i列的上下两行选或不选的情况下获得的最大收益，答案记作\(b\)，转移方程很简单，这里就不给出了
最后答案就是\(max(a,b-2m)\)，因为选方案1时yy能来捣乱
为什么能交换的行数小于m也要减去2m :不管怎么选，只要这种情况就一定有\(a\ge b-2m\)
对于方案1最好不要贪心去写，比如：以上下全0的列做分割，把数据分成几个块，把每个块的求出来，再跑最大子段和，细节较多，很难写(别问我怎么知道的qaq)

Code

#include<bits/stdc++.h>
using namespace std;
int c,T,n,m,f[2000005],g[2000005][2][2],a[2000005];
string s1,s2;
int fx(char x){
    if(x==48)return -1;
    return 1;
}
void input(){
    cin>>n>>m;
    s1=s2="#";
    getchar();
    for(int i=1;i<=n;i++){
        s1+=getchar();
    }
    getchar();
    for(int i=1;i<=n;i++){
        s2+=getchar();
    }
}
int main(){
    cin>>c>>T;
    while(T--){
        input();
        int maxn=0,sum=0;
        for(int i=1;i<=n;i++){
            int tmp=0;
            if(s1[i]=='1'&&s2[i]=='1')a[i]=2;
            else if(s1[i]=='0'&&s2[i]=='0')a[i]=-2,tmp=1;
            else a[i]=0;
            f[i]=max(f[i-1]+a[i]+tmp,a[i]+tmp);
            maxn=max(maxn,f[i]);
        }
        for(int i=1;i<=n;i++){
            g[i][1][1]=max(0,max(g[i-1][1][1],max(g[i-1][1][0],g[i-1][0][1])))+a[i];
            g[i][1][0]=max(0,max(g[i-1][1][1],g[i-1][1][0]))+fx(s1[i]);
            g[i][0][1]=max(0,max(g[i-1][1][1],g[i-1][0][1]))+fx(s2[i]);
            sum=max(sum,max(g[i][1][1],max(g[i][1][0],g[i][0][1])));
        }
        cout<<max(sum-2*m,maxn)<<endl;
    }
    return 0;
}