梦熊 CSP—S模拟赛 T2youyou不喜欢夏天
原题链接
题目大意
youyou 有一个大小为 2 × n 的网格，每个格子可能是黑色或者白色。 现在 youyou 和 yy 要在这个网格上玩一个游戏：
• youyou 先选取出一个可以为空的 连通块 。
• 之后 yy 可以选择最多 m 列，将这些列上下行的格子颜色互换。
定义一个格子集合 S 为一个连通块，当且仅当 S 中任意两个点可以通过集合 S 内 边相邻 的若干个点连通。youyou 希望最大化最终黑色格子减白色格子的数量，而 yy 希望最小化之。现在 youyou 希望你求出：在双方都采用最优策略的情况下，最终黑色格子减白色格子的数量是多少？
解题思路
考虑 youyou 选出的连通块左右端点被确定为 l , r 。显然，全黑列他会都去选择，全白列他只会选择一个格子，因为这些不受 yy 的影响。考虑一黑一白的列。假如他两个格子都选择，那么贡献为 0， 如果只选择一个黑色的格子，虽然贡献是 1 ，但是可能被 yy
操作变成 − 1 。于是他有两种策略：所有的一黑一白列我们都选择两个。这样 yy 没办法操作。
将 x 个一黑一白列选择一个格子，其余选择两个。这样 yy 可以操作。
发现若 youyou 选择策略二为优，当且仅当至少有 2 m 个一黑一白列他选择了一个格子。否则，我们可以将这些列选择两个格子，显然连通块仍连通，对答案的贡献为 0 ；而原来对答案的贡献为 x − 2 m < 0 。因此，youyou 的策略二，可以视作在 不考虑操作 的情况下选出一个连通块。我们只需求这个连通块的最大权值最后减去2m ，这一部分可以用 dp 实现。youyou 的策略一是经典最大子段和问题，也可以使用 dp 实现。
时间复杂度 O(n)。
暴力代码（80pts）
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
long long g[3][N],c;
long long ans=-2100000000,ans2=-21000000;
long long dp[N][4],f[N];
char s[3][N];
//dp[i][0]表示截止到第i列时选上面一格的最大1-0数量,dp[i][1]表示截止到第i列时选下面一格的最大1-0数量,dp[i][2]表示第i列两格都选的最大1-0数量
int main(){int T;cin>>c>>T;while(T--){int n,m;cin>>n>>m;ans=0;ans2=0;for(int i=1;i<=n;i++)dp[i][0]=dp[i][1]=dp[i][2]=f[i]=0;cin>>(s[1]+1)>>(s[2]+1);for(int i=1;i<=2;i++){for(int j=1;j<=n;j++){if(s[i][j]=='1')g[i][j]=1;else g[i][j]=-1;//cout<<g[i][j]<<" ";}//cout<<endl; }//最大子段和思想 for(int i=1;i<=n;i++){long long x=g[1][i]+g[2][i];if(x==-2)x=-1;f[i]=max(f[i-1]+x,x);ans=max(f[i],ans);//cout<<"f["<<i<<"]="<<f[i]<<" ";}//cout<<endl;//cout<<"dp["<<1<<"][0]="<<dp[1][0]<<" dp["<<1<<"][1]="<<dp[1][1]<<" dp["<<1<<"][2]="<<dp[1][2]<<endl;for(int i=1;i<=n;i++){dp[i][0]=max(max(dp[i-1][0]+g[1][i],dp[i-1][2]+g[1][i]),g[1][i]); dp[i][1]=max(max(dp[i-1][1]+g[2][i],dp[i-1][2]+g[2][i]),g[2][i]); dp[i][2]=max( max( max(dp[i-1][2]+g[1][i]+g[2][i],dp[i-1][0]+g[1][i]+g[2][i]) , dp[i-1][1]+g[1][i]+g[2][i] ), g[1][i]+g[2][i]);ans2=max( max(dp[n][0],max(dp[n][1],dp[n][2]) ) ,ans2);//cout<<"dp["<<i<<"][0]="<<dp[i][0]<<" dp["<<i<<"][1]="<<dp[i][1]<<" dp["<<i<<"][2]="<<dp[i][2]<<endl;}ans=max(ans,ans2-m*2);cout<<ans<<endl;//m*2原因:若交换一个0和一个1则0的数量加1,1的数量减1,则总体数量就会减2 }return 0;
}