http://www.elijahqi.win/2017/12/10/loj6005「网络流-24-题」最长递增子序列/ 题目描述
给定正整数序列 x1∼xn x_1 \sim x_n x1∼xn，以下递增子序列均为非严格递增。
计算其最长递增子序列的长度 s s s。 计算从给定的序列中最多可取出多少个长度为 s s s 的递增子序列。 如果允许在取出的序列中多次使用 x1 x_1 x1 和 xn x_n xn，则从给定序列中最多可取出多少个长度为 s s s 的递增子序列。输入格式
文件第 1 1 1 行有 1 1 1 个正整数 n n n，表示给定序列的长度。接下来的 1 1 1 行有 n n n 个正整数 x1∼xn x_1 \sim x_n x1∼xn。 输出格式
第 1 1 1 行是最长递增子序列的长度 s s s。第 2 2 2 行是可取出的长度为 s s s 的递增子序列个数。第 3 3 3 行是允许在取出的序列中多次使用 x1 x_1 x1 和 xn x_n xn 时可取出的长度为 s s s 的递增子序列个数。 样例 样例输入
4 3 6 2 5
样例输出
2 2 3
数据范围与提示
1≤n≤500 1 \leq n \leq 500 1≤n≤500
觉得自己真心废柴啊 什么都想不出这个建图方法想了半天也没想到的x
然后n*log(n)的dp也写不对 好丧啊
首先这个n*log(n)的dp是 设b数组为长度为下标的最小值是多少
那么我每次二分找一下比我小的最小值 然后记下他的长度更新我当前的dp值
然后这条件二和条件三应该怎么满足
可以知道 dp[i]表示一定选i号这个 并且以i结尾的最长上升子序列长度最长是多少
那么所有dp[i]=1的地方一定是起点 所有dp[i]=ans1的地方一定是终点
然后把每个数拆成两个点 中间权值为1 表示限制着一个数只能用一次
然后循环的时候 因为最长上升子序列是递增的所以我每回需要向后扫描 观察什么时候我dp[j]=dp[i]+1 并且满足a[j]>=a[i]的时候表明我有可能能从这里转移过去我建一条权值为1 的点 跑最大流即可
最后 针对第三问只需要把和1或者n有关的点改成无穷的权值即可
#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; }