【JZOJ5489】海明距离

2023-10-25 02:48

文章标签 距离海明 jzoj5489

本文主要是介绍【JZOJ5489】海明距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

设有一长度为n的初始每个位置均为0的序列A。再给定一个长度为n的01序列B。
有Q个特殊的区间[li,ri]，你可以选择将A中li到ri这些位置都变为1，当然你可以选择不变。
现在你需要最小化A,B的海明距离。即最小化对应数值不同的位置数目。

Solution

这题我们可以从暴力入手。将区间按左端点排序后，每次枚举一个区间选不选，加上他的贡献，分与前面的区间相交和不交两种情况。

仔细分析一下暴力，我们可以发现暴力实际上只有两维状态：当前做到的区间 $i$ ，和上一个区间覆盖的最后位置 $j$ 。有这两个我们就可以设状态 $f_{i,j}$ 表示最小海明距离，那么对于一个区间 $[l_i,r_i]$ ，我们可以这样转移（ $s_i$ 表示B序列 $i$ 位置以及之前有多少个 $1$ ）：
$f_{i,r_i}=min(f_{i-1,j}+r_i-max(j,l_i-1)-2(s_{r_i}-s_{max(j,l_i-1)}))(j<r_i)$
$f_{i,j}=f_{i-1,j}(j\geq r_i)$

然后很明显，第一维可以去掉。

把式子拆一拆发现可以用数据结构维护。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
#define N 200100
#define inf 1010580540
using namespace std;
struct node{int l,r;
}b[N];
int a[N],s[N],w[N],n;
int f[N];
struct tree{int f,sf;
}tr[N*4];
bool cmp(node x,node y){return x.l<y.l || (x.l==y.l && x.r<y.r);
}
int min(int x,int y){return x<y?x:y;
}
void update(int v){tr[v].f=min(tr[v*2].f,tr[v*2+1].f);tr[v].sf=min(tr[v*2].sf,tr[v*2+1].sf);
}
void build(int v,int l,int r){if(l==r){tr[v].f=f[l],tr[v].sf=2*s[l]-l+f[l];return;}int mid=(l+r)/2;build(v*2,l,mid),build(v*2+1,mid+1,r);update(v);
}
void insert(int v,int l,int r,int x){if(l==r){if(tr[v].f>f[l]){tr[v].f=f[l],tr[v].sf=f[l]+2*s[l]-l;}return;}int mid=(l+r)/2;x<=mid?insert(v*2,l,mid,x):insert(v*2+1,mid+1,r,x);update(v);
}
int find(int v,int l,int r,int x,int y,int t){if(x>y) return inf;if(l==x && r==y) return !t?tr[v].f:tr[v].sf;int mid=(l+r)/2;if(y<=mid) return find(v*2,l,mid,x,y,t);else if(x>mid) return find(v*2+1,mid+1,r,x,y,t);else return min(find(v*2,l,mid,x,mid,t),find(v*2+1,mid+1,r,mid+1,y,t));
}
int main()
{int m;scanf("%d",&n);fo(i,1,n) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];scanf("%d",&m);memset(f,60,sizeof(f));fo(i,1,m) scanf("%d %d",&b[i].l,&b[i].r);sort(b+1,b+m+1,cmp);fo(i,1,m) w[i]=b[i].r-b[i].l+1-2*(s[b[i].r]-s[b[i].l-1]);f[0]=s[n];build(1,0,n);fo(i,1,m){f[b[i].r]=min(f[b[i].r],min(find(1,0,n,0,b[i].l-1,0)+w[i],find(1,0,n,b[i].l,b[i].r-1,1)+b[i].r-2*s[b[i].r]));insert(1,0,n,b[i].r);}int ans=s[n];fo(i,0,n) ans=min(ans,f[i]);printf("%d",ans);
}