记录编号	361556	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 最长递增子序列	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-01-04 15:54:29	内存使用	61.98 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1005,INF=0x3f3f3f3f;
int n,a[maxn],len=1,s,t,head[maxn];
struct _tree{int to,next,c,f;}e[maxn*maxn*4];
void _Set(int prt,int son,int cap){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,
	e[len].c=cap,e[len].f=0;	
}
void _set(int prt,int son,int cap){
	_Set(prt,son,cap),_Set(son,prt,0);	
}
void _in(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
}
int h[maxn],f[maxn],cnt=0;
int _pre(){
	h[0]=-INF;int i,l,r,mid;
	for(i=1;i<=n;i++)
		if(a[i]>=h[cnt])h[++cnt]=a[i],f[i]=cnt;
		else{
			l=1,r=cnt;
			while(l^r){
				mid=(l+r)>>1;
				if(h[mid]<=a[i])l=mid+1;
				else r=mid;	
			}
			h[l]=a[i],f[i]=l;
		}
	return cnt;
}
#define to e[i].to
int _min(int a,int b){return a<b?a:b;}
bool en[maxn];int Dp[maxn],vis[maxn],tim=0,cur[maxn];queue<int>q;
bool _bfs(){
	vis[s]=++tim,Dp[s]=0;int i,rt;q.push(s);
	while(!q.empty()){
		rt=q.front(),q.pop();
		for(i=head[rt];i;i=e[i].next)
		if(e[i].c>e[i].f&&vis[to]^tim)
			vis[to]=tim,Dp[to]=Dp[rt]+1,q.push(to);	
	}
	return vis[t]==tim;
}
int _dfs(int rt,int v){
	if(rt==t||v==0)return v;
	int flow=0,tmp;
	for(int &i=cur[rt];i;i=e[i].next)
	if(Dp[to]==Dp[rt]+1){
		tmp=_dfs(to,_min(v,e[i].c-e[i].f));	
		if(tmp>0){
			flow+=tmp,e[i].f+=tmp,e[i^1].f-=tmp,v-=tmp;
			if(!v)break;	
		}
	}
	return flow;
}
int _run(){
	int i,flow=0;
	while(_bfs()){
		for(i=s;i<=t;i++)cur[i]=head[i];
		flow+=_dfs(s,INF);
	}
	return flow;
}
int _run(int v){
	if(v==1){
		int i,j;s=0,t=n<<1|1,len=1;memset(head,0,sizeof(head));
		for(i=1;i<=n;i++){
			_set(i*2-1,i*2,1);
			if(f[i]==1)_set(s,i*2-1,INF);
			if(f[i]==cnt)_set(i*2,t,INF);
		}
		for(i=1;i<=n;i++)
		for(j=i-1;j;j--)
			if(a[j]<=a[i]&&f[i]==f[j]+1)_set(j*2,i*2-1,1);
	}
	else{
		_set(1*2-1,1*2,v),_set(n*2-1,n*2,v);
	}
	return _run();
}
void _out(){
	int ans1=_pre();
	if(ans1==1){printf("%d\n%d\n%d\n",ans1,n,n);return;}
	int ans2=_run(1),ans3=ans2+_run(INF);
	printf("%d\n%d\n%d\n",ans1,ans2,ans3);
}
void _work(){
	_in();
	_out();
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("alis.in","r",stdin);
	freopen("alis.out","w",stdout);
#endif
	_work();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
}
//g++ asd.cpp -o asd