题目
题目描述
问题描述：
给定正整数序列x1,…,xn。
（1）计算其最长不下降子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的不下降子序列。
编程任务：
设计有效算法完成（1）（2）（3）提出的计算任务。
输入输出格式
输入格式：
第1行有1个正整数n，表示给定序列的长度。
接下来的1行有n个正整数n:x1,…,xn。
输出格式：
第1 行是最长不下降子序列的长度s。
第2行是可取出的长度为s的不下降子序列个数。
第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s的不下降子序列个数。
输入输出样例
输入样例#1：
4
3 6 2 5
输出样例#1：
2
2
3
说明
$n\leq 500$
题解
第1问是简单的动态规划，第2，3问考虑用网络流解决
我们可以想出这样一个模型：把后面较大的数和前面较小的数连边，然后针对每个长度为$s$的序列第一个数与汇点连，最后一个数与源点连
然后跑最大流就行了
后面较大的数和前面较小的数连边，可以$dp$的时候顺带解决
主要是找序列的第一个数和最后一个数
所以我们两次$dp$：第一次处理从数$i$向前最长的非降子序列（即$f_i$），第二次处理从数$i$向后最长的非降子序列（即$g_i$）
然后若$f_i=s$，源点与$i$连
若$g_i=s$，汇点与$i$连
第2问连边容量都为1，第3问在第二问基础上把源点与最后一个数、第一个数与汇点连边容量改为$inf$（我代码里重建了边）
问题就解决了
注意$s$可能为1，需要特判
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<queue>
using namespace std;
const int MAX=1e5+1,t=1e5,inf=1e8;
struct p{
int x,y,dis;
}c[MAX<<2];
int n,num=2;
int h[MAX],d[MAX],a[MAX],f[MAX],g[MAX];
bool use[MAX];
int read()
{
int x=0,f=1;
char ch=getchar();
for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*f;
}
void add(int x,int y,int dis)
{
c[num]=(p){h[y],x,0},h[y]=num++;
c[num]=(p){h[x],y,dis},h[x]=num++;
}
bool bfs()
{
queue<int> qu;
qu.push(0);
memset(d,0,sizeof(d));
d[0]=1;
while(!qu.empty())
{
int tt=qu.front();
qu.pop();
for(int i=h[tt];i;i=c[i].x)
if(!d[c[i].y]&&c[i].dis)
{
d[c[i].y]=d[tt]+1;
qu.push(c[i].y);
}
}
return d[t];
}
int dfs(int x,int dix)
{
if(x==t||!dix) return dix;
int sum=0;
for(int i=h[x];i;i=c[i].x)
if(d[c[i].y]==d[x]+1&&c[i].dis)
{
int dis=dfs(c[i].y,min(c[i].dis,dix));
if(dis)
{
dix-=dis;
sum+=dis;
c[i].dis-=dis;
c[i^1].dis+=dis;
if(!dix) break;
}
}
if(!sum) d[x]=-1;
return sum;
}
int dinic()
{
int tot=0;
while(bfs()) tot+=dfs(0,inf);
return tot;
}
int main()
{
n=read();
int s=1;
for(int i=1;i<=n;i++)
a[i]=read(),f[i]=g[i]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
if(a[i]>=a[j]&&f[i]<f[j]+1)
f[i]=f[j]+1;
s=max(s,f[i]);
for(int j=1;j<i;j++)
if(a[i]>=a[j]&&f[i]==f[j]+1)
add(i,j,1);
}
for(int i=n-1;i>=1;i--)
for(int j=n;j>i;j--)
if(a[i]<=a[j]&&g[i]<g[j]+1)
g[i]=g[j]+1;
printf("%d\n",s);
if(s==1)
{
printf("%d\n%d",n,n);
return 0;
}
for(int i=1;i<=n;i++)
{
if(f[i]==s) add(0,i,1);
if(g[i]==s) add(i,t,1);
}
printf("%d\n",dinic());
memset(c,0,sizeof(c));
memset(h,0,sizeof(h));
num=2;
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)
if(a[i]>=a[j]&&f[i]==f[j]+1)
add(i,j,1);
for(int i=1;i<=n;i++)
{
if(f[i]==s)
if(i==1||i==n) add(0,i,inf);
else add(0,i,1);
if(g[i]==s)
if(i==1||i==n) add(i,t,inf);
else add(i,t,1);
}
printf("%d",dinic());
return 0;
}
