1 条题解
-
0
考虑贪心,首先一个显然的结论 通过交换变成 ,那么所有 的相对位置必然不变。
那么我们就可以得到每个 可能存在区间。
想让美丽值最大,就要考虑尽量让 直接放在一起。
那就直接贪心,可以放在一起就放在一起。
注意此时有一个问题,就是 可能可以放在最前面更优(比如样例一),因为这样可以让 尽量放在一起。
所以分别对 和 做一遍贪心,取一个最大值就好了。
代码
#include<bits/stdc++.h> using namespace std; const int N=3e5+5; int n,m; char a[N],b[N]; struct Line{int l,r;}p[N]; vector<int> veca,vecb; int solve(int x){ if(!x)return 0; return x-1; } int work(){ int S=0; veca.clear(),vecb.clear(); for(int i=1;i<=n+m;i++){ if(a[i]=='0')veca.push_back(i); if(b[i]=='0')vecb.push_back(i); } for(int i=0;i<n;i++)p[i+1]=(Line){min(veca[i],vecb[i]),max(veca[i],vecb[i])}; int x=1; p[n+1].r=n+m+1; while(x<=n){ int now=p[x].r,s=0; s++; while(p[x+1].l<=now+1&&x<n){ now++,s++,x++; } S+=s-1; S+=solve(p[x+1].r-now-1); x++; } S+=solve(p[1].r-1); return S; } int ans; int main(){ scanf("%d%d",&n,&m); scanf("%s",a+1); scanf("%s",b+1); ans=work(); for(int i=1;i<=n+m;i++){ if(a[i]=='0')a[i]='1';else a[i]='0'; if(b[i]=='0')b[i]='1';else b[i]='0'; } swap(n,m); ans=max(ans,work()); printf("%d",ans); }
- 1
信息
- ID
- 66
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者