题目描述
«问题描述：
给定正整数序列x1,...,xn 。
（1）计算其最长不下降子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的不下降子序列。
«编程任务：
设计有效算法完成（1）（2）（3）提出的计算任务。
输入输出格式
输入格式：
第1 行有1个正整数n，表示给定序列的长度。接下来的1 行有n个正整数n:x1, ..., xn。
输出格式：
第1 行是最长不下降子序列的长度s。第2行是可取出的长度为s 的不下降子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的不下降子序列个数。
输入输出样例
输入样例#1：
43 6 2 5
输出样例#1：
223
说明
n\le 500n≤500
这里我们先说明下题意：
第二问里用过的元素不能再用，即取出的最多的不重叠的最长不下降子序列数量
而第3问里，x1，xn可以重复用，但是出现过一次的序列不能再出现
搞明白他要什么了之后就可以考虑构图了
针对每个数智能用一次的限制，我们可以让i裂成$i$和$i'$
从$i$到$i'$连一条1的边，就可以保证只用一次
接下来我们考虑如何在各个点之间连边
在第一问时我们处理出$f[i]$，从i出发所能接出的最长序列
不难发现，无论拿出的时哪几个序列，如果要充分利用的话，$i$必然向$f[j]==f[i]-1$的$j$连边
所以我们对于每个$i'$，找到所有能接在它后面且$f[j]==f[i]-1$的$j$，连$i'->j$为1
最后对于所有$f[i]==s$的连$S-inf->i$，$f[i]==1$的连$i'-inf->T$
至于为什么是inf嘛。。是为了方便1和n，当然这里可以分别处理吧（懒得想了
1 #include2 #define N 2005 3 #define M 300000 4 #define INF (1<<30) 5 using namespace std; 6 int h[N],to[M],nxt[M],fl[M],etop; 7 int S=0,T=2000,n,x[505],f[505]; 8 void add(int u,int v,int w){ 9 //printf("%d %d %d\n",u,v,w);10 to[etop]=v,nxt[etop]=h[u],fl[etop]=w,h[u]=etop++;11 to[etop]=u,nxt[etop]=h[v],fl[etop]=0,h[v]=etop++;12 }13 queue q;14 int lev[N];15 inline bool bfs(){16 memset(lev,-1,sizeof(lev));17 lev[S]=0;q.push(S);18 while(!q.empty()){19 int u=q.front();q.pop();20 for(int k=h[u];~k;k=nxt[k]){21 int v=to[k];22 if(lev[v]==-1&&fl[k]){23 lev[v]=lev[u]+1;24 q.push(v);25 }26 }27 }28 return lev[T]!=-1;29 }30 int dfs(int u,int t,int left){31 if(u==t)return left;32 for(int k=h[u];~k;k=nxt[k]){33 int v=to[k];34 if(lev[v]==lev[u]+1&&fl[k]){35 int d=dfs(v,t,min(left,fl[k]));36 if(d){37 fl[k]-=d;38 fl[k^1]+=d;39 return d;40 }41 }42 }43 return 0;44 }45 int dinic(){46 int flow=0,f;47 while(bfs()){48 while(f=dfs(S,T,INF))flow+=f;49 }50 return flow;51 }52 int s;53 void pre(){54 for(int i=n;i>=1;i--){55 for(int j=i+1;j<=n;j++)56 if(x[i]<=x[j])f[i]=max(f[i],f[j]);57 f[i]++;58 s=max(s,f[i]);59 }60 }61 int main(){62 scanf("%d",&n);63 for(int i=1;i<=n;i++)scanf("%d",&x[i]);64 pre();65 printf("%d\n",s);66 if(s==1){67 printf("%d\n%d",n,n);68 return 0;69 }70 memset(h,-1,sizeof(h));71 for(int i=1;i<=n;i++){72 add(i<<1,i<<1|1,1);73 for(int j=i+1;j<=n;j++)74 if(f[i]==f[j]+1&&x[i]<=x[j])75 add(i<<1|1,j<<1,1);76 if(f[i]==1)add(i<<1|1,T,INF);77 if(f[i]==s)add(S,i<<1,INF);78 }79 printf("%d\n",dinic());80 memset(h,-1,sizeof(h));81 etop=0;82 for(int i=1;i<=n;i++){83 if(i==1||i==n)add(i<<1,i<<1|1,INF);84 else add(i<<1,i<<1|1,1);85 for(int j=i+1;j<=n;j++)86 if(f[i]==f[j]+1&&x[i]<=x[j])87 add(i<<1|1,j<<1,1);88 if(f[i]==1)add(i<<1|1,T,INF);89 if(f[i]==s)add(S,i<<1,INF);90 }91 printf("%d\n",dinic());92 return 0;93 }94 /*95 696 4 7 1 6 4 397 */
当然如果你也这样连边，别忘了特判坑爹的s==1，不然会出正无穷的。。。