记录编号	221127	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 最长递增子序列	最终得分	100
用户昵称	23333	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2016-01-21 20:17:45	内存使用	14.08 MiB

#include<bits/stdc++.h>
#define inf 214748347
#define N 1023
#define rep(i,l,r) for(int i=l;i<=r;i++)
int head[N],dis[N],tot=1,n,T,sum,ans,a[N],cur[N],f[N],k;
using namespace std;
struct Edge{
   int to,next,w;
}e[1201000];
inline void ins(int u,int v,int w) {
   e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w;
}
inline int read() {
	 int x=0; char ch=getchar();
	 while(ch<'0' || ch>'9') ch=getchar();
	 while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
	 return x;
}
inline bool bfs(){
   rep(i,0,T) dis[i]=-1; queue<int>q; q.push(0); dis[0]=0;
   while(!q.empty()) {
   	 int x=q.front(); q.pop();
  	 for(int k=head[x];k;k=e[k].next) 
 	    if(dis[e[k].to]<0 && e[k].w>0) {
 	    	  dis[e[k].to]=dis[x]+1; q.push(e[k].to);
 	    }
   }
   if(dis[T]>0) return 1;else return 0;
}
int find(int x,int low){
   if(x==T) return low;
   int delta=low,now;
   for(int k=cur[x];k;k=e[k].next) 
     if(e[k].w>0 && dis[e[k].to]==dis[x]+1){ 
         now=find(e[k].to,min(e[k].w,delta));
         e[k].w-=now; e[k^1].w+=now;   delta-=now;
         if(!delta){
         	 cur[x]=k;return low;
         }	
      } 
   dis[x]=-1;
   return low-delta;
}
void Dinic() {
	 while(bfs()) {
	 	 memcpy(cur,head,(T+1)<<2); while(sum=find(0,inf)) ans+=sum;
	 }
}
int main () {
   freopen("alis.in","r",stdin); freopen("alis.out","w",stdout);
   n=read(); rep(i,1,n)a[i]=read();  T=n+n+1;
   rep(i,1,n) {
   	 f[i]=1; rep(j,1,i-1) if(a[j]<=a[i]) f[i]=max(f[i],f[j]+1);
		k=max(k,f[i]);
   }
   printf("%d\n",k);
   
   rep(i,1,n) ins(i,i+n,1),ins(i+n,i,0);
   rep(i,1,n) if(f[i]==1)ins(0,i,1),ins(i,0,0);else if(f[i]==k) ins(i+n,T,1),ins(T,i+n,0);
   rep(i,1,n) 
     rep(j,i+1,n) if(a[j]>=a[i] && 1+f[i]==f[j])  ins(i+n,j,1),ins(j,i+n,0);
   Dinic();
   if(!ans)printf("%d\n",n);else printf("%d\n",ans); ans=0;
   
   memset(head,0,(T+1)<<2);   tot=1;
   rep(i,2,n-1) ins(i,i+n,1),ins(i+n,i,0);
   rep(i,2,n-1)	if(f[i]==1) ins(0,i,1),ins(i,0,0);else if(f[i]==k) ins(i+n,T,1),ins(T,i+n,0);
   ins(1,1+n,inf),ins(1+n,1,0); if(f[1]==1) ins(0,1,inf),ins(1,0,0);else if(f[1]==k) ins(1+n,T,inf),ins(T,1+n,0);
   ins(n,n+n,inf),ins(n+n,n,0); if(f[n]==1) ins(0,n,inf),ins(n,0,0);else if(f[n]==k) ins(n+n,T,inf),ins(T,n+n,0);
   rep(i,1,n)
     rep(j,i+1,n) if(a[j]>=a[i] && f[i]+1==f[j])  ins(i+n,j,1),ins(j,i+n,0);
   Dinic();
   if(!ans)printf("%d\n",n);else printf("%d\n",ans); ans=0;
   fclose(stdin); fclose(stdout);
   return 0;
}