Processing math: 100%

#C231116D. 最长不下降子序列(lis)


#C231116D. 最长不下降子序列(lis)

网址(Website)

题目详情 - 最长不下降子序列(lis) - Super

题解 - 最长不下降子序列(lis) - Super

题目(Problem)

大意:给出 01 串,第一行为段数 n ,接下来每行 2 个整数 ai,biai 表示当前段是 0 还是 1bi 表示个数,给定 m ,表示询问数,对于每次操作:

  1. 区间翻转,翻转任意区间(reverse);
  2. 输出翻转后能达到的最长不下降子序列长度;

注意

  1. 输入: 第一行一个整数 n,表示 01 串的段数。 接下来 n 行每行两个整数 aibiai0,1 表示第 i 段是全 0 还是全 1bi 表示第 i 段的长度。保证 i[2,n]aiai1 。第 n+2 行一个整数 m
  2. 输出:共有 m+1 行,输出翻转后能达到的最长不下降子序列长度,==其中第一行为原 01 串的 lis 长度==,后面 m 行表示每次操作。

范围1n2×1050mnai0,11bi109

题解(Solution)

70pts

对于一个 lis ,找到一个位置 i ,使 [1,i1]0 的个数与 [i+1n]1 的个数的加和有最大值。

考虑转化:先计算出所有的 1 的个数,然后把 0 的值设为 11 的值设为 1 ,原问题便转化为每次反转一个区间,求每次反转后最大的前缀和,即每次的最长不下降子序列为 summax+tot1。(其中 tot1 代表 1 的总数)

那么我们再来考虑每次翻转,很明显,如果当前的翻转取得了一个最优的 ans ,对总体来说也是最优的,那么就可以用贪心的思想。怎么翻转才能使答案有最优解呢?

  • 找到一个不在当前的 ans 计算的区间里面的 [l,r][1,n] ,将这个区间放在要计入的 ans 里面,一定有正贡献;
  • 替换一部分区间出来(要不然 ans 的值不会被影响),这个区间不好寻找,但是我们知道,在该区间被替换出去以后, ans 就变成了 sumzsumy1+sumx1 ,其中 [y,z] 代表有最大正贡献的区间, [x,y1] 代表要被替换掉的区间。而当前的最大贡献区间已经求出来了,我们就只需要找到前面的最大的 sumx1 就可以了。

对于每一次操作,倒着处理一遍,可以在 O(n) 的时间内处理出来,总时间复杂度 O(n2) ,可以拿 70pts 。注意,每次操作替换时后,一定要判断 sumzsumy1+sumx1 是否大于 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

后续(Ending)


文章作者: WolfDeer
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 WolfDeer !