# loj6005「网络流 24 题」最长递增子序列

xiaoxiao2021-02-28  7

http://www.elijahqi.win/2017/12/10/loj6005「网络流-24-题」最长递增子序列/ 题目描述

4 3 6 2 5

2 2 3

1≤n≤500 1 \leq n \leq 500 1≤n≤500

#include<queue> #include<cstdio> #include<cstring> #include<algorithm> #define N 1100 #define inf 0x3f3f3f3f using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; } inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x; } int n,b[N],a[N],dp[N],num=1,h[N],level[N],T; struct node{ int y,z,next; }data[N*N]; inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].next=h[x];data[num].z=z;h[x]=num; data[++num].y=x;data[num].next=h[y];data[num].z=0;h[y]=num; } inline bool bfs(){ memset(level,0,sizeof(level));queue<int>q;q.push(0);level[0]=1; while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[y]||!z) continue;level[y]=level[x]+1;q.push(y);if (y==T) return 1; } }return 0; } inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(z,s));s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!xx) level[y]=0; if (!s) return ss; } }return ss-s; } int main(){ freopen("loj.in","r",stdin); n=read();int ans1=0;T=n*2+1; for (int i=1;i<=n;++i) a[i]=read();memset(b,0x3f,sizeof(b));b[1]=a[1];dp[1]=1; for (int i=2;i<=n;++i){ int len=upper_bound(b+1,b+n+1,a[i])-b-1;dp[i]=len+1; if(a[i]<b[len+1]) b[len+1]=a[i];ans1=max(ans1,len+1); }printf("%d\n",ans1);int ans=0; //for (int i=1;i<=n;++i) printf("%d ",dp[i]);printf("\n"); for (int i=1;i<=n;++i) { if (dp[i]==1) insert1(0,i,1);insert1(i,i+n,1); if (dp[i]==ans1) insert1(i+n,T,1); for (int j=i+1;j<=n;++j) if (dp[j]==dp[i]+1&&a[j]>=a[i]) insert1(i+n,j,1); } while(bfs()) ans+=dfs(0,inf);printf("%d\n",ans);num=1;memset(h,0,sizeof(h));ans=0; for (int i=1;i<=n;++i) { if (dp[i]==1) insert1(0,i,i==1?inf:1); if(i==1||i==n) insert1(i,i+n,inf);else insert1(i,i+n,1); if (dp[i]==ans1) insert1(i+n,T,i==n?inf:1); for (int j=i+1;j<=n;++j) if (dp[j]==dp[i]+1&&a[j]>=a[i]) insert1(i+n,j,1); }while(bfs()) ans+=dfs(0,inf);printf("%d\n",ans); return 0; }