#C231116D. 最长不下降子序列(lis)
网址(Website)
题目(Problem)
大意:给出 01 串,第一行为段数 n ,接下来每行 2 个整数 ai,bi, ai 表示当前段是 0 还是 1 ,bi 表示个数,给定 m ,表示询问数,对于每次操作:
- 区间翻转,翻转任意区间(reverse);
- 输出翻转后能达到的最长不下降子序列长度;
注意:
- 输入: 第一行一个整数 n,表示 01 串的段数。 接下来 n 行每行两个整数 ai,bi。ai∈0,1 表示第 i 段是全 0 还是全 1,bi 表示第 i 段的长度。保证 ∀i∈[2,n],ai≠ai−1 。第 n+2 行一个整数 m。
- 输出:共有 m+1 行,输出翻转后能达到的最长不下降子序列长度,==其中第一行为原 01 串的 lis 长度==,后面 m 行表示每次操作。
范围:1≤n≤2×105;0≤m≤n;ai∈0,1;1≤bi≤109 。
题解(Solution)
70pts
对于一个 lis ,找到一个位置 i ,使 [1,i−1] 中 0 的个数与 [i+1,n] 中 1 的个数的加和有最大值。
考虑转化:先计算出所有的 1 的个数,然后把 0 的值设为 1 , 1 的值设为 −1 ,原问题便转化为每次反转一个区间,求每次反转后最大的前缀和,即每次的最长不下降子序列为 summax+tot1。(其中 tot1 代表 1 的总数)
那么我们再来考虑每次翻转,很明显,如果当前的翻转取得了一个最优的 ans ,对总体来说也是最优的,那么就可以用贪心的思想。怎么翻转才能使答案有最优解呢?
- 找到一个不在当前的 ans 计算的区间里面的 [l,r]⊆[1,n] ,将这个区间放在要计入的 ans 里面,一定有正贡献;
- 替换一部分区间出来(要不然 ans 的值不会被影响),这个区间不好寻找,但是我们知道,在该区间被替换出去以后, ans 就变成了 sumz−sumy−1+sumx−1 ,其中 [y,z] 代表有最大正贡献的区间, [x,y−1] 代表要被替换掉的区间。而当前的最大贡献区间已经求出来了,我们就只需要找到前面的最大的 sumx−1 就可以了。
对于每一次操作,倒着处理一遍,可以在 O(n) 的时间内处理出来,总时间复杂度 O(n2) ,可以拿 70pts 。注意,每次操作替换时后,一定要判断 sumz−sumy−1+sumx−1 是否大于 ans ,如果小于,那么说明此时的 ai 数组已经有了最长的 lis ,就没有翻转的必要了。
100pts
代码(Code)
70pts
c++ language-none
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 201234;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n,m,a[N],sum[N],res;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("lis.in","r",stdin);
freopen("lis.out","w",stdout);
n=input();For(i,1,n){
int x=input(),y=input();if(x) a[i]=-y,res+=y;
else a[i]=y;
}m=input();
for(int i=1;i<=m+1;++i){
int mx=0;for(int j=1;j<=n;j++) sum[j]=sum[j-1]+a[j],mx=max(mx,sum[j]);
cout<<mx+res<<'\n';if(i==m+1) break;
int l=1,r=1;
int sy=-inf,y=0,sz=-inf,z=0;
for(int j=n;j>=1;j--){
if(sum[j]>sz) sz=sum[j],z=j;
if(sz-sum[j-1]>sy) sy=sz-sum[j-1],y=z;
if(sy+sum[j-1]>mx) mx=sy+sum[j-1],l=j,r=y;
}reverse(a+l,a+r+1);
}return 0;
}
100pts
c++ language-none