【线性规划与网络流24题 6】最长递增子序列

Description

给定正整数序列x1, .., xn。
（1）计算其最长递增子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。
（3）如果允许在取出的序列中多次使用x1和 xn，则从给定序列中最多可取出多少个长度为s的递增子序列。

编程任务：
设计有效算法完成（1）（2）（3）提出的计算任务。

Input

第1 行有 1个正整数n(n<500)，表示给定序列的长度。
接下来的1 行有 n个正整数x1, ..., xn.

Output

程序运行结束时，将任务（1）（2）（3）的解答输出。
第1 行是最长递增子序列的长度s。第2行是可取出的长度为s的递增子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s的递增子序列个数。

Sample Input

4
3 6 2 5

Sample Output

2
2
3

第一问呢：

二维的线性dp搞法：dp【i】为以i结尾的，最长不下降子序列的长度

然后，枚举1~i-1进行转移

第二问：

要求长度为s的非下降子序列的个数

就是求最大流：那我们需要考虑如何建边

因为每个点只能使用一次：使用经典的拆边方法咯：

每个点拆成u1和u2，边上的容量为1

如何实现转移：

如果dp【i】=dp【j】+1，并且a【i】>=a【j】（貌似这个条件是废话），而且i>j，说明i在j之后

那么，连接一条j2到i1的容量为1的边，表示可以实现转移

源点S与dp【x】为1的所有x连边，容量为1，代表从这儿出发（不能与所有点相连，因为这样长度到不了s）

dp【x】为s的所有x与汇点T连边，容量为1

第三问：

1号点和n号点可以使用无数次的话，意味着增加边权就好！

注意：有可能增加边权之后，答案变成了2*INF！（想想为什么：当原数列是下降序列的时候，第二问答案为n，拆点之后，相当于S到T有了容量为2*INF的边）

所以要注意判断下，是不是这种情况

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn=10050;
const int maxm=100500;
const int INF=99999999;

struct Edge{
	int to,nxt,cap,flow;
}edge[maxm];
int tol,Head[maxn];

void init(){
	memset(Head,-1,sizeof(Head));
	tol=2;
}

void addedge(int u,int v,int w,int rw=0){
	edge[tol].to=v;
	edge[tol].cap=w;
	edge[tol].flow=0;
	edge[tol].nxt=Head[u];
	Head[u]=tol++;
	
	edge[tol].to=u;
	edge[tol].cap=rw;
	edge[tol].flow=0;
	edge[tol].nxt=Head[v];
	Head[v]=tol++;
}

int Q[maxn],dep[maxn],cur[maxn],sta[maxn];

bool bfs(int s,int t,int n){
	int front=0,tail=0;
	memset(dep,-1,sizeof(dep[0])*(n+1));
	dep[s]=0;
	Q[tail++]=s;
	while(front<tail){
		int u=Q[front++];
		for(int i=Head[u];i!=-1;i=edge[i].nxt){
			int v=edge[i].to;
			if (edge[i].cap>edge[i].flow&&dep[v]==-1){
				dep[v]=dep[u]+1;
				if (v==t) return true;
				Q[tail++]=v;
			}
		}
	}
	return false;
}

int dinic(int s,int t,int n){
	int maxflow=0;
	while(bfs(s,t,n)){
		for(int i=0;i<n;i++) cur[i]=Head[i];
		int u=s,tail=0;
		while(cur[s]!=-1){
			if (u==t) {
				int tp=INF;
				for(int i=tail-1;i>=0;i--) 
					tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
				maxflow+=tp;
				for(int i=tail-1;i>=0;i--){
					edge[sta[i]].flow+=tp;
					edge[sta[i]^1].flow-=tp;
					if (edge[sta[i]].cap-edge[sta[i]].flow==0) tail=i;
				}
				u=edge[sta[tail]^1].to;
			}
			else if (cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
				sta[tail++]=cur[u];
				u=edge[cur[u]].to;
			}
			else{
				while(u!=s&&cur[u]==-1) u=edge[sta[--tail]^1].to;
				cur[u]=edge[cur[u]].nxt;
			}
		}
	}
	return maxflow;
}

int dp[maxn];
int a[maxn];
int s,t,tot,n;

int getpoint1(int x){
	return x*2-1;
}

int getpoint2(int x){
	return x*2;
}

/*
void calc(int len,int val){
	init();
	addedge(getpoint1(1),getpoint2(1),val);
	addedge(getpoint1(n),getpoint2(n),val);
	for(int i=2;i<n;i++)
		addedge(getpoint1(i),getpoint2(i),1);
	for(int i=1;i<=n;i++){
		if (dp[i]==1)
			addedge(s,getpoint1(i),INF);
		if (dp[i]==len)
			addedge(getpoint2(i),t,INF);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			if (a[i]>=a[j]&&dp[i]==dp[j]+1)
				addedge(getpoint2(j),getpoint1(i),1);
	int ans=dinic(s,t,tot);
	printf("%d\n",ans);
}
*/

int main(){
	//freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		int ans=0;
		for(int i=1;i<=n;i++){
			dp[i]=1;
			for(int j=1;j<i;j++)
				if (a[i]>=a[j])
					dp[i]=max(dp[i],dp[j]+1);
			ans=max(ans,dp[i]);
		}
		printf("%d\n",ans);
		s=0;t=2*n+1;tot=t+1;
		//calc(ans,1);
		//calc(ans,INF);
		init();
		addedge(getpoint1(1),getpoint2(1),1);
		addedge(getpoint1(n),getpoint2(n),1);
		for(int i=2;i<n;i++)
			addedge(getpoint1(i),getpoint2(i),1);
		for(int i=1;i<=n;i++){
			if (dp[i]==1)
				addedge(s,getpoint1(i),INF);
			if (dp[i]==ans)
				addedge(getpoint2(i),t,INF);
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<i;j++)
				if (a[i]>=a[j]&&dp[i]==dp[j]+1)
					addedge(getpoint2(j),getpoint1(i),1);
		ans=dinic(s,t,tot);
		printf("%d\n",ans);
		addedge(getpoint1(1),getpoint2(1),INF);
		addedge(getpoint1(n),getpoint2(n),INF);
		int temp=dinic(s,t,tot);
		if (temp<INF) ans+=temp;
		printf("%d\n",ans);
	}
	return 0;
}