Description

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

Input

第一行包括一个整数n。
接下来一行n个整数，描述序列B。
输入一行一个整数Q。
接下来Q行，每行两个整数li,ri 。

Output

输出最小的海明距离。

Sample Input

输入1：

9
0 1 0 1 1 1 0 1 0
3
1 4
5 8
6 7

输入2：

15
1 1 0 0 0 0 0 0 1 0 1 1 1 0 0
9
4 10
13 14
1 7
4 14
9 11
2 6
7 8
3 12
7 13

Sample Output

输出1：

3

输出2：

5

Data Constraint

Solution

• 首先将区间按左端点从小到大排序，依次处理。

• 设 f[i] 表示做到第 i 个区间时对答案的贡献（即不选的答案 - 最优答案）。

• 再设 p[i] 表示从 1 到 i 的答案贡献前缀和（当前位置是 1 则加一，0 则减一）。

• 那么转移区间 i 就有两种情况：

• 当区间 j 与区间 i 没有相交（r[j]<l[i]） ，则：

  f[i]=max{f[j]+sum[r[i]]−sum[l[i]−1]}

• 当区间 j 与区间 i 相交了（l[i]≤r[j]） ，则：

  f[i]=max{f[j]+sum[r[i]]−sum[r[j]]}

• 那么我们只需用线段树维护一下 f[i] 和 f[i]−sum[r[i]] 两个值的最大值来转移即可。

• 时间复杂度 O(N log N) 。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; const int N=2e5+1; struct data {int x,y; }g[N<<2],b[N]; int sum,ans; int a[N],f[N],p[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool cmp(data x,data y) {return x.x<y.x || x.x==y.x && x.y<y.y; } inline int max(int x,int y) {return x>y?x:y; } inline void change(int v,int l,int r,int x,int y,bool pd) {if(l==r){if(pd) g[v].y=y; else g[v].x=y;return;}int mid=l+r>>1;if(x<=mid) change(v<<1,l,mid,x,y,pd); else change(v<<1|1,mid+1,r,x,y,pd);if(pd) g[v].y=max(g[v<<1].y,g[v<<1|1].y); else g[v].x=max(g[v<<1].x,g[v<<1|1].x); } inline int find(int v,int l,int r,int x,int y,bool pd) {if(l>=x && r<=y) return pd?g[v].y:g[v].x;int mid=l+r>>1;if(y<=mid) return find(v<<1,l,mid,x,y,pd);if(x>mid) return find(v<<1|1,mid+1,r,x,y,pd);return max(find(v<<1,l,mid,x,mid,pd),find(v<<1|1,mid+1,r,mid+1,y,pd)); } int main() {int n=read();for(int i=1;i<=n;i++){sum+=a[i]=read();p[i]=p[i-1]+(a[i]?1:-1);}int m=read();for(int i=1;i<=m;i++) b[i].x=read(),b[i].y=read();sort(b+1,b+1+m,cmp);memset(g,128,sizeof(g));memset(f,128,sizeof(f));for(int i=1;i<=m;i++){int num=b[i].x-1?find(1,1,n,1,b[i].x-1,false):0;if(num<0) num=0;f[i]=max(f[i],num+p[b[i].y]-p[b[i].x-1]);num=find(1,1,n,b[i].x,b[i].y,true);f[i]=max(f[i],num+p[b[i].y]);change(1,1,n,b[i].y,f[i],false);change(1,1,n,b[i].y,f[i]-p[b[i].y],true);ans=max(ans,f[i]);}printf("%d",sum-ans);return 0; }

总结

以上是生活随笔为你收集整理的JZOJ 5489. 【清华集训2017模拟11.28】海明距离的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。