记录编号	147794	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 最长递增子序列	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-02-04 08:04:12	内存使用	2.05 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,i,p,zj1,zj2,zj3=0,ans=0,ST,SD;
const int INF=1e8;

int to[150000]={0},ne[150000]={0},w[150000]={0},head[1010]={0},sj=1;
void Addedge(int u,int v,int z)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=z;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj,w[sj]=0;
}
int que[1010]={0},que_head=1,que_tail=0;
int GET(){int x=que[que_head];que[0]--;if((++que_head)==1010)que_head=1;return x;}
void PUSH(int x){que[0]++;if((++que_tail)==1010)que_tail=1;que[que_tail]=x;}

int d[510]={0},f[1010]={0};
void Build(int X,int W)
{
	//sj=1;memset(head,0,sizeof(head));
	for(i=1;i<=n;i++)Addedge((i<<1)-1,i<<1,1);
 	//Addedge(1,2,W);Addedge((n<<1)-1,n<<1,W);
	for(i=1;i<=n;i++)
	{
		if(f[i]==1)Addedge(ST,(i<<1)-1,INF);
    	if(f[i]==X)Addedge(i<<1,SD,INF);
	}
	for(i=1;i<=n;i++)for(p=1;p<i;p++)
	if(d[i]>=d[p]&&f[i]==f[p]+1)Addedge(p<<1,(i<<1)-1,1);
}

void init()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&d[i]);
	ST=(n<<1)+1,SD=ST+1;
	for(i=1;i<=n;i++)
	{
		for(f[i]=1,p=1;p<i;p++)
		if(d[i]>=d[p]&&f[p]>=f[i])f[i]=f[p]+1;
		if(f[i]>ans)ans=f[i];
	}
	printf("%d\n",ans);
}

int pre[1010]={0},cur[1010]={0};
void isap()
{
    int cnt[1010]={0},lv[1010]={0};
	PUSH(SD);
    while(que[0])
	for(zj1=GET(),i=head[zj1];i;i=ne[i])
	if(w[i^1]&&!lv[to[i]])
	cnt[lv[to[i]]=lv[zj1]+1]++,PUSH(to[i]);
	cnt[lv[SD]]--,cnt[lv[SD]=0]=SD;
	for(i=1;i<=SD;i++)cur[i]=head[i];
	int U=ST;pre[ST]=ST,zj1=INF;bool flag;
	while(lv[ST]<SD)
	{
		//cout<<U<<"  "<<"dfssdf"<<endl;
		for(flag=0,i=cur[U];i;i=ne[i])
		{
			if(w[i]&&lv[to[i]]==lv[U]-1)
			{
				flag=1,pre[to[i]]=U,U=to[i];
				if(w[i]<zj1)zj1=w[i];
				if(U==SD)
				{
					while(U!=ST)
					U=pre[U],w[cur[U]]-=zj1,w[cur[U]^1]+=zj1;
					ans+=zj1,zj1=INF;
				}
				break;
			}
			cur[U]=ne[i];
		}
		if(flag)continue;
		if(!(--cnt[lv[U]]))break;
		for(zj2=SD+1,i=head[U];i;i=ne[i])
		if(w[i]&&zj2>lv[to[i]])zj2=lv[to[i]],cur[U]=i;
		cnt[lv[U]=zj2+1]++,U=pre[U];
	}
}

void End_()
{
	zj3=ans;ans=0;
	Build(zj3,1);isap();
	if(ans>n)ans=n;
	printf("%d\n",ans);
	Addedge(1,2,INF);Addedge((n<<1)-1,n<<1,INF);
	//Build(zj3,INF);
	isap();
	if(ans>n)ans=n;
	printf("%d\n",ans);
}

int main()
{
	//freopen("a.txt","r",stdin);
	freopen("alis.in","r",stdin);
	freopen("alis.out","w",stdout);
	init();
	End_();
	//while(1);
	return 0;
}