记录编号	361308	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 最长递增子序列	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2017-01-03 18:07:46	内存使用	3.76 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1010,M=1e5+10;
int n,len,a[N],d[N],g[N];
int find(int x){
	int l=0,r=len;
	while (l!=r){
		int mid=(l+r)>>1;
		if (g[mid+1]<=x) l=mid+1;else r=mid;
	}
	return l;
}
struct edge{
	int f,t,g,o;
	edge(int F=0,int T=0,int G=0,int O=0){
		f=F;t=T;g=G;o=O;
	}
}w[M];
int cnt,head[M],tail[M],next[M];
void add(int f,int t,int g){
	++cnt;w[cnt]=edge(f,t,g,cnt+1);
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	++cnt;w[cnt]=edge(t,f,0,cnt-1);
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
struct st{
	int x,i,df;
	st(int X=0,int DF=0){x=X;i=head[x];df=DF;}
}z[M];
int ans,s,t,l[M],top;
#define V z[top].x
#define E z[top].i
#define F z[top].df
void change(){
	int df=F;ans+=df;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[w[z[i].i].o].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
queue<int> Q;
void bfs(){
	for (int i=s;i<=t;i++) l[i]=0;
	l[s]=1;Q.push(s);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t);
	}
}
bool dinic(){
	bfs();
	if (!l[t]) return 0;
	z[top=1]=st(s,1e9);
	while (top){
		if (V==t){change();top--;E=next[E];continue;}
		if (!E){l[V]=0;top--;E=next[E];continue;}
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=st(w[E].t,min(F,w[E].g)),top++;
		else E=next[E];
	}
	return 1;
}
void init(){
	for (int i=1;i<=cnt;i++) next[i]=0;
	ans=cnt=0;
	for (int i=s;i<=t;i++) head[i]=0;
}
int main()
{
	freopen("alis.in","r",stdin);
	freopen("alis.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		d[i]=find(a[i])+1;
		if (d[i]>len) g[++len]=a[i];
		g[d[i]]=min(g[d[i]],a[i]);
	}
	printf("%d\n",len);
	if (len==1) printf("%d\n%d\n",n,n),exit(0);
	s=0;t=n*2+1;
	for (int i=1;i<=n;i++){
		add(i,i+n,1);
		if (d[i]==1) add(s,i,1e9);
		if (d[i]==len) add(i+n,t,1e9);
		for (int j=i+1;j<=n;j++)
			if (a[j]>=a[i]&&d[j]==d[i]+1) add(i+n,j,1);
	}
	while (dinic());
	printf("%d\n",ans);
	init();
	for (int i=1;i<=n;i++){
		add(i,i+n,1);
		if (d[i]==1) add(s,i,1e9);
		if (d[i]==len) add(i+n,t,1e9);
		for (int j=i+1;j<=n;j++)
			if (a[j]>=a[i]&&d[j]==d[i]+1) add(i+n,j,1);
		if (i==1||i==n) add(i,i+n,1e9);
	}
	while (dinic());
	printf("%d\n",ans);
	return 0;
}