问题 A: 最大K段和

时限: 1 Sec  内存: 128 MB

题目描述

fzszkl有一个长度为N的序列A 。他希望从中选出不超过K个连续子段，满足它们两两不相交，求总和的最大值（可以一段也不选，答案为 0）。

输入格式

第一行输入两个正整数 N，K 。 第二行输入 N个整数Ai 。

输出格式

输出一行一个非负整数表示答案。

输入样例

7 2 -1 9 -2 6 -8 1 -7

输出样例

15

提示

N,M<=10^5

 

 

 

题解

明显WQS二分（虽然不知道是不是凸函数）（应该是凸函数吧）

然后把每个位置都加了一个权。。。调了1.5h，以为是自己的二分或check写错了，各种换二分姿势。。。

后来发现对每个位置加权连单调性都没有（因为增大加权可以减少段数，减小加权也可以减少段数）。。。更别说凸了

于是就。。。。。。人没了

其实应该对每一个要选的段加一个权

然后单调队列DP，又由于它没有决策点的左端的限制，所以直接记一下最大值的位置就好了，注意特判

WQS二分最重要的就是：限制什么的个数，就对什么加权（当然前提是凸函数）

代码：  

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int gi() { char c;int num=0,flg=1; while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1; while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();} return num*flg; } #define N 100005 #define LL long long const LL INF=0x3f3f3f3f3f3f3f3fll; int a[N],g[N],n; LL sum[N],f[N]; int check(LL mid) { int mx=0; for(int i=1;i<=n;i++){ if(f[mx]+sum[i]-sum[mx]+mid>f[i-1]||(f[mx]+sum[i]-sum[mx]+mid==f[i-1]&&g[mx]+1<g[i])) f[i]=f[mx]+sum[i]-sum[mx]+mid,g[i]=g[mx]+1; else f[i]=f[i-1],g[i]=g[i-1]; if(f[i]-sum[i]>f[mx]-sum[mx]||(f[i]-sum[i]==f[mx]-sum[mx]&&g[i]<g[mx])) mx=i; } return g[n]; } int main() { int k,i,cnt=0;LL tmp=0; n=gi();k=gi(); for(i=1;i<=n;i++){ a[i]=gi(); sum[i]=sum[i-1]+1ll*a[i]; if(a[i]>0)tmp+=1ll*a[i],cnt++; } if(cnt<k){ printf("%lld",tmp); return 0; } LL l,r,mid,ans=0; l=-INF;r=0; while(l<=r){ mid=(l+r)>>1; if(check(mid)<=k){ ans=mid; l=mid+1; } else r=mid-1; } check(ans); printf("%lld",f[n]-1ll*ans*k); }

其实还有一个加强版本：https://www.luogu.org/problem/CF280D（带修改+区间查询）

这道题有一点模拟费用流的思想（就有点像可以反悔的贪心）

把选走的区间的所有数乘一个-1

然后用线段树大力维护就可以了

 

 

 

问题 B: 双端队列xLIS问题

时限: 1 Sec  内存: 128 MB

题目描述

fzszkl有N个数Ai ，他准备将他们依次插入一个双端队列（每次可以在头或尾插入一个元素），最后将 整个队列从尾到头看成一个序列，求出最长上升子序列的长度L 。他想知道， L的最大值是多少。 序列A 的一个上升子序列的严谨定义：从一个序列中删掉若干（可以为0 ）个数，剩下的数满足对于任意i<j,Ai<Aj ，则称剩下的数为原序列的一个上升子序列。

输入格式

第一行输入一个正整数 N。 第二行输入N个正整数Ai 。

输出格式

输出一行一个正整数表示答案。

输入样例

8 1 9 2 6 8 1 7 1926817

输出样例

5

提示

插入时，分别选择头头尾头头尾头头，得到的序列为1,2,1,9,6,8,7,1926817，最长上升子序列为1,2,6,8,1926817 ，长度为5 。可以证明，不存在更优的方案能构造出更长的上升子序列。   对于所有数据，满足：1<=N<=10^5,1<=Ai<=10^9 

 

 

 

 

题解

首先对于一个数，从它开始的最长上升子序列是必定排在它后面的

然后观察了一下性质，发现1 9 2是永远不能排列为成1 2 9的

但是2 1 3可以排列为1 2 3

于是可以推理出：一个数，如果它后面有数比它小，则这个较小的数可以排到它的前面

但是又发现这些较小的数必须是一个递减子序列

所以答案就是从一个数开始的最长上升子序列+最长下降子序列-1

代码：  

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int gi() { char c;int num=0,flg=1; while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1; while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();} return num*flg; } #define N 100005 int a[N],tmp[N],b[N],f[N],g[N]; int main() { int n,i,len=1; n=gi(); for(i=1;i<=n;i++) a[i]=gi(); for(i=1;i<=n;i++) tmp[i]=a[n-i+1]; len=0; for(i=1;i<=n;i++){ int j=lower_bound(b+1,b+len+1,tmp[i])-b; b[j]=tmp[i]; if(j==len+1)len++; f[i]=j; } for(i=1;i<=n;i++) tmp[i]=-a[n-i+1]; memset(b,0,sizeof(b)); len=0; for(i=1;i<=n;i++){ int j=lower_bound(b+1,b+len+1,tmp[i])-b; b[j]=tmp[i]; if(j==len+1)len++; g[i]=j; } int ans=1; for(i=1;i<=n;i++) ans=max(ans,f[i]+g[i]-1); printf("%d",ans); }

 

 

 

 

问题 C: 最大前缀和

时限: 1 Sec  内存: 128 MB

题目描述

输入格式

输入两个正整数N和M，表示1的数量和-1的数量 (N<=2000,M<=2000)

输出格式

输出答案对998244853(是个质数）取模的值。

输入样例

2 2

输出样例

5

提示

本质不同的序列有6种。  [1,1,-1,-1]，最大前缀和为 2；  [1,-1,1,-1] ，最大前缀和为1 ；  [1,-1,-1,1] ，最大前缀和为1 ；  [-1,1,1,-1] ，最大前缀和为1 ；  [-1,1,-1,1] ，最大前缀和为0;  [-1,-1,1,1]，最大前缀和为0. 

 

 

 

题解

先从数据范围自然想到一个O(n^3)的DP

然后又调了1h，最后发现自己有一个地方没有+1（我*……#@*￥……）！）

代码：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int mod=998244853; int f[205][105][105]; int n,m,ans; int cnt1,cnt_1; void dfs(int i,int mx) { if(i>n+m){ ans+=mx; if(ans>=mod)ans-=mod; return; } if(cnt1<n){ cnt1++; dfs(i+1,max(mx,cnt1-cnt_1)); cnt1--; } if(cnt_1<m){ cnt_1++; dfs(i+1,max(mx,cnt1-cnt_1)); cnt_1--; } } int main() { int i,j,k; scanf("%d%d",&n,&m); if(n<=10&&m<=10){ dfs(1,0); printf("%d",ans); } else if(n<=100&&m<=100){ f[0][0][0]=1; for(i=0;i<n+m;i++) for(j=0;j<=i;j++)if(i-j<=m&&j<=n) for(k=0;k<=j;k++){ if(!f[i][j][k])continue; if(j+1<=n)(f[i+1][j+1][max(j+1-(i-j),k)]+=f[i][j][k])%=mod; if(i+1-j<=m)(f[i+1][j][max(j-(i+1-j),k)]+=f[i][j][k])%=mod; } int sum=0; for(i=max(n-m,0);i<=n;i++){ sum+=1ll*f[n+m][n][i]*i%mod; if(sum>=mod)sum-=mod; } printf("%d",sum); } }

 

然后有因为是+1 -1，自然想到括号序列——>卡特兰数——>直线翻折

我们把+1 -1分别看成上走一步和右走一步

然后问题就转换为求点(0,0)到点(n,m)的路径，每条路径的加权为该路径上的所有点(i,j)的max(i-j，0)

点（0,0）到点（a，b）（只能右上走和右下走）且不超过直线y=x+b的方案数为：

点（0,0）到点（a，b）的所有方案 - 点（0,0）关于y=x+b的对称点到（a，b）的所有方案

于是就可以O(n)了

代码：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int mod=998244853; int f[205][105][105]; int n,m,ans; int cnt1,cnt_1; void dfs(int i,int mx) { if(i>n+m){ ans+=mx; if(ans>=mod)ans-=mod; return; } if(cnt1<n){ cnt1++; dfs(i+1,max(mx,cnt1-cnt_1)); cnt1--; } if(cnt_1<m){ cnt_1++; dfs(i+1,max(mx,cnt1-cnt_1)); cnt_1--; } } int jcinv[2005],jc[2005]; int ksm(int x,int y) { int ans=1; while(y){ if(y&1)ans=1ll*ans*x%mod; y>>=1;x=1ll*x*x%mod; } return ans; } void shai() { jcinv[0]=jc[1]=jc[0]=1; for(int i=2;i<=2000;i++) jc[i]=1ll*jc[i-1]*i%mod; jcinv[2000]=ksm(jc[2000],mod-2); for(int i=1999;i>=1;i--) jcinv[i]=1ll*jcinv[i+1]*(i+1)%mod; } int C(int x,int y) { return 1ll*jc[x]*jcinv[y]%mod*jcinv[x-y]%mod; } int main() { //freopen("maxpsum.in","r",stdin); //freopen("maxpsum.out","w",stdout); int i,j,k; scanf("%d%d",&n,&m); if(n<=10&&m<=10){ dfs(1,0); printf("%d",ans); } else if(n<=100&&m<=100){ f[0][0][0]=1; for(i=0;i<n+m;i++) for(j=0;j<=i;j++)if(i-j<=m&&j<=n) for(k=0;k<=j;k++){ if(!f[i][j][k])continue; if(j+1<=n)(f[i+1][j+1][max(j+1-(i-j),k)]+=f[i][j][k])%=mod; if(i+1-j<=m)(f[i+1][j][max(j-(i+1-j),k)]+=f[i][j][k])%=mod; } int sum=0; for(i=max(n-m,0);i<=n;i++){ sum+=1ll*f[n+m][n][i]*i%mod; if(sum>=mod)sum-=mod; } printf("%d",sum); } else{ shai(); int ans=0,pre=0; for(i=n-m;i<=n;i++){ int t=((C(n+m,n)-C(n+m,i+m+1))%mod-pre)%mod; if(i>0)ans=(1ll*ans+1ll*t*i)%mod; pre=(1ll*pre+1ll*t)%mod; } printf("%d",ans); } }