题意
给定\(n,x,y\)和两个01串,字符串的长度为\(n\),现在你可以选择一个\(l\)和\(r\)(\(1\leq{l}<{r}\leq{n}\)),将\(a_l\)变成\(1-a_l\),将\(a_r\)变成\(1-a_r\),\(l+1=r\),则代价是\(x\),否则代价是\(y\),操作次数不限,求使两个串相同的最小代价,若无解输出-1
题解
设两个01串有\(cnt\)个位置不同,如果\(cnt\)为奇数,显然无解
如果\(cnt\)是偶数,以下进行分类讨论
-
\(x\geq{y}\)
特判一下\(cnt=2\)且这两个位置是相邻的情况,此时的答案为\(min(2*y,x)\)
否则,我们总可以选\(cnt/2\)组不相邻的位置(因为选相邻总是不优的),此时答案为\(cnt/2*y\)
-
\(x<y\)
处理出所有两个01串不同的位置,原问题等价于把这些位置分成\(cnt/2\)组,每组的策略如下:
设这两个位置是\(l\)和\(r\),相邻的话显然直接操作,不相邻的话,直接操作或者移动某个位置,直到相邻后再操作
因此,最小代价为\(min(y,(r-l)*x)\)
我们在pos数组上考虑区间dp,考虑区间\([l,r]\),我们可以证明dp只有三种情况:\(l,l+1\)同组,\(r,r-1\)同组,\(l,r\)同组
预处理区间长度为2的情况,只dp区间长度为偶数的区间,答案即为\(f[1][cnt]\)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5007;
ll n,x,y,a[N],b[N],f[N][N],pos[N];
void read(ll &x){
char c=getchar();
x=0;
while(!isdigit(c)){
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
}
ll read(){
char c=getchar();
while(c!='0'&&c!='1'){
c=getchar();
}
return c-'0';
}
ll calc(ll l,ll r){
return min((r-l)*x,y);
}
void work(){
ll i,j,cnt=0;
read(n),read(x),read(y);
for(i=1;i<=n;++i){
a[i]=read();
}
for(i=1;i<=n;++i){
b[i]=read();
}
for(i=1;i<=n;++i){
if(a[i]!=b[i]){
pos[++cnt]=i;
}
}
if(cnt%2){
puts("-1");
return;
}
if(x>=y){
if(cnt==2&&pos[2]-pos[1]==1){
printf("%lld\n",min(2*y,x));
}
else{
printf("%lld\n",cnt/2*y);
}
}
else{
for(i=1;i<cnt;++i){
f[i][i+1]=calc(pos[i],pos[i+1]);
}
for(i=4;i<=cnt;i+=2){
for(j=1;j+i-1<=cnt;++j){
ll l=j,r=j+i-1;
f[l][r]=min(min(f[l+2][r]+calc(pos[l],pos[l+1]),f[l][r-2]+calc(pos[r-1],pos[r])),
f[l+1][r-1]+calc(pos[l],pos[r]));
}
}
printf("%lld\n",f[1][cnt]);
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
work();
}
return 0;
}
标签:cnt,min,read,ll,Hard,pos,Zero,D2,getchar
From: https://www.cnblogs.com/DGJG/p/16712169.html