最长不下降子序列问题 - 网络流

题目描述

给定正整数序列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\le 500n≤500

第一问：直接dp即可，处理出 dp[i] 代表以 i 结尾的最长不下降子序列。
第二问：用流量表示个数，拆点防止一个点用多次，那么怎么保证每次流过去的都是长度为 s 的呢？我们把源点S连向dp值为1的，dp值为s的连向汇点T，就能保证长度一定为s了。然后如果 a[j]<=a[i] && dp[j]+1 == dp[i] 那么我们就可以连边。
第三问：端点可以用多次，我们直接让s连向1节点的流量为inf，拆点后的1节点内部流量为inf （因为端点dp值肯定为1），因为n节点dp值不一定为s，所以我们特判一下即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1010,M=100010;
const int inf=0x3f3f3f3f;
int n,dp[N],a[N],h[N],s,t,len=1,res;
int head[N],nex[M],to[M],w[M],tot=1;
inline void ade(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
int bfs(){
	memset(h,0,sizeof h);	queue<int> q;	q.push(s);	h[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	} 
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi;	w[i^1]+=mi;	fl+=mi;	f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,inf);
	return res;
}
signed main(){
	cin>>n; 	s=0;	t=2*n+2;
	for(int i=1;i<=n;i++)	cin>>a[i];	dp[1]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++)	if(a[j]<=a[i])	dp[i]=max(dp[i],dp[j]+1);
		dp[i]=max(dp[i],1);	len=max(len,dp[i]);
	}
	cout<<len<<endl;
	for(int i=1;i<=n;i++){
		add(i,i+n,1);
		if(dp[i]==1)	add(s,i,1);	if(dp[i]==len)	add(i+n,t,1);
		for(int j=1;j<i;j++)	if(a[j]<=a[i]&&dp[j]+1==dp[i])	add(j+n,i,1);
	}
	cout<<(res=dinic())<<endl;
	add(s,1,inf);	add(1,1+n,inf);
	if(dp[n]==len)	add(n,n+n,inf),add(n+n,t,inf);
	cout<<dinic()+res<<endl;
	return 0;
}