首页 > 代码库 > [网络流24题]最长递增子序列问题
[网络流24题]最长递增子序列问题
题目大意:给定长度为n的序列a,求:1.最长递增子序列长度;2.最多选出几个不相交的最长递增子序列;3.最多选出几种在除了第1个和第n个以外的地方不相交的最长递增子序列。(n<=1000)
思路:先倒着DP,求出f[i]表示以a[i]开头的最长的递增子序列长度,然后建图,若f[i]=最长递增子序列长度则S向i连1,若f[i]=1则i向T连1,若i<j且a[i]<a[j]且f[i]=f[j]+1则i向j连1,为保证每个点只被流一次,拆成入点和出点,流量限制1,跑最大流即可解决第二问,点1和点n的流量限制改为INF则可解决第三问,这样建图边数看上去是O(n^2)的,实际上比这小很多,是可过的,另外边其实是可以优化到O(n)的,由于f[i]相同的点若下标递增则a[i]不升,我们对每个i找到最大的j满足a[i]<a[j]且f[i]=f[j]+1连1,再找到最大的j满足j<i且f[i]=f[j]连INF,容易发现这样建图和原图效果是一样的。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read() { int x;char c; while((c=getchar())<‘0‘||c>‘9‘); for(x=c-‘0‘;(c=getchar())>=‘0‘&&c<=‘9‘;)x=(x<<3)+(x<<1)+c-‘0‘; return x; } #define MN 1000 #define MV 2000 #define ME 1000000 #define S MV+1 #define T MV+2 #define INF 0x7FFFFFFF struct edge{int nx,t,w;}e[ME*2+5]; int n,h[MV+5],en=1,a[MN+5],f[MN+5],mx,d[MV+5],q[MV+5],qn,c[MV+5]; inline void ins(int x,int y,int w) { e[++en]=(edge){h[x],y,w};h[x]=en; e[++en]=(edge){h[y],x,0};h[y]=en; } void build(int v) { for(int i=1;i<=n;++i) { ins(i,i+n,(i>1&&i<n)||!v?1:INF); if(!f[i])ins(i+n,T,i==n&&v?INF:1); if(f[i]==mx)ins(S,i,i==1&&v?INF:1); for(int j=i;++j<=n;)if(a[i]<=a[j]&&f[i]==f[j]+1)ins(i+n,j,1); } } bool bfs() { int i,j; memset(d,0,sizeof(d)); for(d[q[i=qn=0]=S]=1;i<=qn;++i)for(j=c[q[i]]=h[q[i]];j;j=e[j].nx) if(e[j].w&&!d[e[j].t])d[q[++qn]=e[j].t]=d[q[i]]+1; return d[T]; } int dfs(int x,int r) { if(x==T)return r; int k,u=0; for(int&i=c[x];i;i=e[i].nx)if(e[i].w&&d[e[i].t]==d[x]+1) { k=dfs(e[i].t,min(r-u,e[i].w)); u+=k;e[i].w-=k;e[i^1].w+=k; if(u==r)return u; } return d[x]=0,u; } int main() { int i,j,ans=0;n=read(); for(i=1;i<=n;++i)a[i]=read(); for(i=n;--i;mx=max(mx,f[i]))for(j=n;j>i;--j) if(a[i]<=a[j])f[i]=max(f[i],f[j]+1); printf("%d\n",mx+1); for(build(0);bfs();)ans+=dfs(S,INF); printf("%d\n",ans); memset(h,ans=0,sizeof(h));build(en=1); while(bfs())ans+=dfs(S,INF); printf("%d",ans); }
[网络流24题]最长递增子序列问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。