首页 > 代码库 > codevs1906 最长递增子序列问题
codevs1906 最长递增子序列问题
题目描述 Description
给定正整数序列x1,..... , xn 。
（1）计算其最长递增子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长
度为s的递增子序列。
输入描述 Input Description
第1 行有1个正整数n，表示给定序列的长度。接
下来的1 行有n个正整数x1.....xn 。
输出描述 Output Description
第1 行是最长递增子序列的长度s。第2行是可取出的长度为s 的递增子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的递增子序列个数。
样例输入 Sample Input
4
3 6 2 5
样例输出 Sample Output
2
2
3
不得不吐槽codevs上面网络流24题好多数据都是很蛋疼的要输出方案又不给spj……鬼知道你数据是用哪种方案啊
啊这题还算正常
第一问LIS随便求
第二问拆点完S向所有x1连流量1费用0的边，所有x2向T连流量1费用0的边，所有x1向x2连流量1费用1的边。因为要表示有没有取这个点
对于所有a[i]<a[j]且i<j的，i2向j1连流量1费用0的边
然后跑最大费用。每次增广搞完如果答案是第一问的最长长度，那么ans++。
第三问就是第二问的建图与1和n有关的边的流量全改inf就对了
#include<cstdio>#include<iostream>#include<cstring>#define LL long long#define inf 0x3ffffff#define S 0#define T 1001using namespace std;inline LL read(){ LL 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-‘0‘;ch=getchar();} return x*f;}int n,ans,flow,cnt,tot;int a[510];int mn[510];struct edge{int from,to,next,v,c;}e[500010];int head[1010],dis[1010],q[1010],from[1010];bool mrk[1010];inline void ins(int u,int v,int w,int c){ e[++cnt].to=v; e[cnt].v=w; e[cnt].c=c; e[cnt].from=u; e[cnt].next=head[u]; head[u]=cnt;}inline void insert(int u,int v,int w,int c){ ins(u,v,w,c); ins(v,u,0,-c);}inline int bsearch(int x){ int l=1,r=ans,s=0; while(l<=r) { int mid=(l+r)>>1l; if (mn[mid]<=x){s=mid;l=mid+1;} else r=mid-1; } return s;}inline bool spfa(){ for (int i=1;i<=T;i++)dis[i]=inf; memset(mrk,0,sizeof(mrk)); int t=0,w=1; dis[S]=0;q[0]=S;mrk[S]=1; while (t!=w) { int now=q[t++];if (t==1005)t=0; for (int i=head[now];i;i=e[i].next) if (e[i].v&&dis[now]+e[i].c<dis[e[i].to]) { dis[e[i].to]=dis[now]+e[i].c; from[e[i].to]=i; if (!mrk[e[i].to]) { mrk[e[i].to]=1; q[w++]=e[i].to; if (w==1005)w=0; } } mrk[now]=0; } if (dis[T]==inf)return 0; return 1;}inline void mcf(){ int x=inf;flow=0; for (int i=from[T];i;i=from[e[i].from]) x=min(x,e[i].v); for (int i=from[T];i;i=from[e[i].from]) { e[i].v-=x; e[i^1].v+=x; flow+=x*e[i].c; } if (flow==-ans)tot++;}int main(){ n=read(); for (int i=1;i<=n;i++)a[i]=read(); ans=1;mn[1]=a[1]; for (int i=2;i<=n;i++) { int fnd=bsearch(a[i]); if (fnd==ans)mn[++ans]=a[i]; else mn[fnd+1]=a[i]; } printf("%d\n",ans); cnt=1; for(int i=1;i<=n;i++) { insert(S,i,1,0); insert(i+n,T,1,0); insert(i,i+n,1,-1); } for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (a[i]<=a[j])insert(i+n,j,1,0); while (spfa())mcf(); printf("%d\n",tot); memset(head,0,sizeof(head)); cnt=1;tot=0; insert(S,1,inf,0);insert(S,n,inf,0); insert(1+n,T,inf,0);insert(2*n,T,inf,0); insert(1,1+n,inf,-1);insert(n,2*n,inf,-1); for(int i=1;i<=n;i++) { insert(S,i,1,0); insert(i+n,T,1,0); insert(i,i+n,1,-1); } for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++) if (a[i]<=a[j]) if (i!=1&&j!=n)insert(i+n,j,1,0); else insert(i+n,j,inf,0); while (spfa())mcf(); printf("%d\n",tot);}
codevs1906 最长递增子序列问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。