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

这是一道看起来很简单的麻题。
很显然可以发现第一问就是直接n^2DP求一个答案。
第二问模拟寻找最长不下降子序列的过程。
第三问改几条边再跑一遍。
但是要注意很多很多细节。
比如说，建模的时候应该反着建。
再比如说，对于最长长度只有1的情况应当格外注意，因为这可能会导致各种错误。
写起来还是有点烦心的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

const int INF=0x3f3f3f3f;
const int BIG=19260817;
inline int Min(int A,int B){
	return A<B?A:B;
}

inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[250005];
int h[2005],et=-1;

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int dep[2005],nw[2005],a[505];
int n,s,t,len;
std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF,nw[i]=h[i];
	}
	dep[s]=1;
	while(!q.empty()){
		q.pop();
	}
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
//	for(int i=1;i<=t;++i){
//		printf("%d ",dep[i]);
//	}
//	puts("");
	return dep[t]^INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
		}
	}
	return cnt;
}
int f[505];
inline void slv1(){
	for(int i=1;i<=n;++i){
		f[i]=1;
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]){
				f[i]=Max(f[i],f[j]+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,f[i]);
	}
	len=ans;
	printf("%d\n",ans);
}

inline int dinic(){
	int RT=0;
	while(bfs()){
		RT+=dfs(s,INF);
	}
	return RT;
}

inline void slv2(){
	s=2*n+1,t=2*n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	et=-1;
	for(int i=1;i<=n;++i){
		if(f[i]==len){
			add(i+n,t,1);
		}
		if(f[i]==1){
			add(s,i,1);
		}
		add(i,i+n,1);
		for(int j=1;j<i;++j){
			if(a[i]>=a[j]&&f[j]+1==f[i]){
				add(j+n,i,1);
			}
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
	add(1,n+1,BIG),add(s,1,BIG);
	if(f[n]==len){
		add(n,2*n,BIG),add(2*n,t,BIG);
	}
	while(bfs()){
		ans+=dfs(s,INF);
	}
	printf("%d\n",ans);
}

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	slv1();
	slv2();
}
int main(){
	init();
	return 0;
}