Cogs 731. [网络流24题] 最长递增子序列(最大流)

[网络流24题] 最长递增子序列 ★★★☆ 输入文件：alis.in 输出文件：alis.out 简单对比 时间限制：1 s 内存限制：128 MB «问题描述： 给定正整数序列x1,…, xn。 （1）计算其最长递增子序列的长度s。 （2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。 （3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长 度为s的递增子序列。 注意：这里的最长递增子序列即最长不下降子序列！！！ «编程任务： 设计有效算法完成（1）（2）（3）提出的计算任务。 «数据输入： 由文件alis.in提供输入数据。文件第1 行有1个正整数n(n<=500)，表示给定序列的长度。接 下来的1 行有n个正整数x1,…, xn。 «结果输出: 程序运行结束时，将任务（1）（2）（3）的解答输出到文件alis.out中。第1 行是最长 递增子序列的长度s。第2行是可取出的长度为s 的递增子序列个数。第3行是允许在取出 的序列中多次使用x1和xn时可取出的长度为s 的递增子序列个数。 输入文件示例 输出文件示例 alis.in 4 3 6 2 5 alis.out 2 2 3 /* 好题. 没想出来。。。 第一问求DPLIS,貌似费用流也行2333. f[i]表示以i为结尾的LIS长度. 第二问和第三问网络流. 因为每个位置只允许用到一次,所以拆点连边. 然后有大小正序关系的连边 (这点想到了,但是没想到是当且仅当f值相差为1的时候. 因为第二问和第三问求的是最长的, 所以f值相差不为1的点显然没必要建边. 第三问的x1,xn疯狂用无非就是该相关边的流量为INF. */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define INF 1e9 #define MAXN 1010 using namespace std; int n,m,S,T,cut=1,f[MAXN],a[MAXN],head[MAXN],dis[MAXN],len,ans; struct edge{int v,next,c;}e[MAXN*MAXN*2]; queue<int>q; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; } void add(int u,int v,int c) { e[++cut].v=v;e[cut].c=c;e[cut].next=head[u];head[u]=cut; e[++cut].v=u;e[cut].c=0;e[cut].next=head[v];head[v]=cut; } void LIS() { for(int i=1;i<=n;i++) { f[i]=1; for(int j=1;j<i;j++) if(a[i]>=a[j]) f[i]=max(f[i],f[j]+1); len=max(len,f[i]); } printf("%d\n",len); } bool bfs() { for(int i=S;i<=T;i++) dis[i]=-1;dis[S]=0;q.push(S); while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]==-1&&e[i].c) dis[v]=dis[u]+1,q.push(v); } } return dis[T]!=-1; } int dfs(int u,int y) { if(u==T) return y; int rest=0; for(int i=head[u];i&&rest<y;i=e[i].next) { int v=e[i].v; if(dis[v]==dis[u]+1&&e[i].c) { int x=dfs(v,min(y-rest,e[i].c)); rest+=x; e[i].c-=x; e[i^1].c+=x; } } if(!rest) dis[u]=-1; return rest; } void dinic() { while(bfs()) ans+=dfs(S,INF); printf("%d\n",ans); } void slove() { S=0,T=2*n+1; for(int i=1;i<=n;i++) add(i,i+n,1); for(int i=1;i<=n;i++) if(f[i]==1) add(S,i,1); for(int i=1;i<=n;i++) if(f[i]==len) add(i+n,T,1); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { if(a[j]>=a[i]&&f[j]==f[i]+1) add(i+n,j,1); } dinic(); } void slove2() { memset(head,0,sizeof head); S=0,T=2*n+1;cut=1;ans=0;add(1,n+1,INF),add(n,2*n,INF);; if(f[1]==1) add(S,1,INF); if(f[n]==len) add(2*n,T,INF); for(int i=2;i<=n-1;i++) add(i,i+n,1); for(int i=2;i<=n-1;i++) if(f[i]==1) add(S,i,1); for(int i=2;i<=n-1;i++) if(f[i]==len) add(i+n,T,1); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { if(a[j]>=a[i]&&f[j]==f[i]+1) add(i+n,j,1); } dinic(); } int main() { freopen("alis.in","r",stdin); freopen("alis.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i]=read(); LIS(); if(len==1){ printf("%d\n%d",n,n);return 0; } slove(); slove2(); return 0; }