P11218 【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天 题解

· · 题解

P11218 【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天 题解

挺好的 dp，感觉难点在于思路转化。

场上 dp 少开了一维，得到了 56pts 的高分，赛后 10min 想出正解，我还是太菜了。

upd：2024/10/24 修改了一点小笔误，望管理员重新审核后通过。

思路

思考一下对于 youyou 和 yy 来说的最优策略是啥。

假设 youyou 选择了一个连通块，并且其中存在一列，youyou 上下都选了，yy 显然不会去交换那一列，因为那样对最终的答案没有影响；如果 youyou 选了某一列一个 0，而另一个没选，yy 也显然不会交换那一列，因为那样对最终答案的影响不优；当且仅当 youyou 选择了某一列的一个 1，而另一个是 0 且 youyou 没选，yy 才会去选择交换。

整理完 yy 的最优策略，对于 youyou 的最优策略也就显然了。对于一列全是 1 来说，youyou 显然会全选；对于一列全是 0 来说，youyou 只可能选其中一个 0，用于延长连通块的长度；对于一列有 1 有 0 来说，youyou 要么全选，要么只选其中的那个 1，显然不可能只选那个 0。

经过一些简单的分析，最终 youyou 想要得到最大的结果，只有可能是在如下两种方案中选择最大值：

第一种方案是显然的，我就不细说了，重点讲一下第二种方案。我们发现，yy 仅会交换选 1 没选 0 的那些列，并且是能换就换，最多交换 m 次。对于最终的答案来说，yy 每做一次有效的交换，都会使最终的答案减少 2，所以最终要把答案减掉 2m。

这时候又会有人说了，如果我第二种方案没有选超过 m 列一 1 一 0 的情况，那答案不是减去 2m，而是减去二倍的有效交换次数。但是你会发现，如果你选择的一 1 一 0 的列数没有超过 m，那么这种方案显然会劣于第一种方案，因为第一种方案会使答案减少的只有上下两个 0 只选一个的情况，然而第二种方案不仅这种情况会使答案减少，那些单选一个 1 的列也会使答案减少，故这种情况我们直接忽略掉就好了。

怎么维护呢？对于第一种方案，我们直接跑一个板子最大子段和就好了，详细的说就是把 00 的列视为 -1，把 10 和 01 的列视为 0，把 11 的列视为 2，然后跑最大子段和。对于第二种操作，显然选择这一列的情况只有三种：“只选上面”，“只选下面”，“上下都选”。然后还是一样的方式去跑最大子段和，只不过注意转移即可。

简单列一下方案二的状态转移方程，设 f_{i,0} 表示第 i 列只选上面，f_{i,1} 表示第 i 列只选下面，f_{i,2} 表示第 i 列上下都选，a_i 表示第 i 列上面的那个数，b_i 表示第 i 列下面那个数，则有：

f_{i,0}=\max\{A,A+f_{i-1,0},A+f_{i-1,2}\} f_{i,1}=\max\{B,B+f_{i-1,1},B+f_{i-1,2}\} f_{i,2}=\max\{A+B,A+B+f_{i-1,0},A+B+f_{i-1,1},A+B+f_{i-1,2}\}

其中 A=[a_i=1]-[a_i=0],B=[b_i=1]-[b_i=0]。

方案二最终的答案为 \max\{f_{i,j}-2m\}。

由于最大子段和的 dp 的时间复杂度为 O(n)，则总时间复杂度为 O(Tn)，足以通过此题。

代码

不错的 dp 题。

#include <iostream>
#include <algorithm>
#define ll int
using namespace std;
const ll N=2e6+10;
string a,b;
ll n,m,f[N][5],ya[N],dp[N];
void solve(){
    cin>>n>>m;
    cin>>a>>b;
    a=' '+a;b=' '+b;
    for(ll i=1;i<=n;i++){
        if(a[i]=='0'&&b[i]=='0') ya[i]=-1;
        if(a[i]=='0'&&b[i]=='1') ya[i]=0;
        if(a[i]=='1'&&b[i]=='0') ya[i]=0;
        if(a[i]=='1'&&b[i]=='1') ya[i]=2;
    }
    ll ans=0;
    for(ll i=1;i<=n;i++){
        if(dp[i-1]+ya[i]<ya[i]) dp[i]=ya[i];
        else dp[i]=dp[i-1]+ya[i];
        ans=max(ans,dp[i]);
    }
    for(ll i=1;i<=n;i++){
        ll A=(a[i]=='1')-(a[i]=='0'),B=(b[i]=='1')-(b[i]=='0');
        f[i][0]=max(A,max(A+f[i-1][0],A+f[i-1][2]));
        f[i][1]=max(B,max(B+f[i-1][1],B+f[i-1][2]));
        f[i][2]=max(max(A+B,A+B+f[i-1][0]),max(A+B+f[i-1][1],A+B+f[i-1][2]));
        ans=max(ans,f[i][0]-2*m);
        ans=max(ans,f[i][1]-2*m);
        ans=max(ans,f[i][2]-2*m);
    }
    cout<<ans<<"\n";
}
ll c,T;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>c>>T;
    while(T--) solve();
    return 0;
}