题目描述
«问题描述：
给定正整数序列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 的递增子序列个数。
输入输出样例
43 6 2 5
223
说明
n≤500n\le 500n≤500
摘自洛谷题解
写的很清楚
首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。
1、把序列每位i拆成两个点<i.a>和<i.b>，从<i.a>到<i.b>连接一条容量为1的有向边。
2、建立附加源S和汇T，如果序列第i位有F[i]=K，从S到<i.a>连接一条容量为1的有向边。
3、如果F[i]=1，从<i.b>到T连接一条容量为1的有向边。
4、如果j>i且A[i] < A[j]且F[j]+1=F[i]，从<i.b>到<j.a>连接一条容量为1的有向边。
求网络最大流，就是第二问的结果。把边(<1.a>,<1.b>)(<N.a>,<N.b>) (S,<1.a>)(<N.b>,T)这四条边的容量修改为无穷大，再求一次网络最大流，就是第三问结果。
【建模分析】
上述建模方法是应用了一种分层图的思想，把图每个顶点i按照F[i]的不同分为了若干层，这样图中从S出发到T的任何一条路径都是一个满足条件的最长上升子序列。
由于序列中每个点要不可重复地取出，需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数，所以最大流量就是第二问结果。
第三问特殊地要求x1和xn可以重复使用，只需取消这两个点相关边的流量限制，求网络最大流即可。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 struct Node 9 { 10 int next,to,c; 11 }edge[2000001],edge2[2000001]; 12 int num=1,head[2001],cur[2001],n,m,dist[2001],ans,sum,maxflow,a[2001]; 13 int f[2001],s,inf=2e9; 14 void add(int u,int v,int c) 15 { 16 num++; 17 edge[num].next=head[u]; 18 head[u]=num; 19 edge[num].to=v; 20 edge[num].c=c; 21 } 22 bool bfs(int S,int T) 23 { int i; 24 memset(dist,-1,sizeof(dist)); 25 queue Q; 26 Q.push(S); 27 dist[S]=1; 28 while (!Q.empty()) 29 { 30 int u=Q.front(); 31 Q.pop(); 32 for (i=head[u];i;i=edge[i].next) 33 { 34 int v=edge[i].to; 35 if (edge[i].c>0&&dist[v]==-1) 36 { 37 dist[v]=dist[u]+1; 38 Q.push(v); 39 } 40 } 41 } 42 if (dist[T]==-1) return 0; 43 return 1; 44 } 45 int dfs(int x,int flow,int des) 46 { 47 int res=0; 48 if (x==des) return flow; 49 for (int &i=cur[x];i;i=edge[i].next) 50 { 51 int v=edge[i].to; 52 if (dist[v]==dist[x]+1&&edge[i].c) 53 { 54 int tmp=dfs(v,min(flow-res,edge[i].c),des); 55 if (tmp<0) continue; 56 edge[i].c-=tmp; 57 edge[i^1].c+=tmp; 58 res+=tmp; 59 if (res==flow) return res; 60 } 61 } 62 return res; 63 } 64 void Dinic(int S,int T) 65 { 66 maxflow=0; 67 while (bfs(S,T)) 68 { 69 memcpy(cur,head,sizeof(cur)); 70 int a=0; 71 while (a=dfs(S,2e9,T)) maxflow+=a; 72 } 73 return; 74 } 75 int main() 76 { int i,j; 77 cin>>n; 78 for (i=1;i<=n;i++) 79 { 80 scanf("%d",&a[i]); 81 } 82 for (i=1;i<=n;i++) 83 { 84 for (j=0;j<=i-1;j++) 85 if (a[i]>=a[j]) 86 f[i]=max(f[i],f[j]+1); 87 s=max(s,f[i]); 88 } 89 for (i=1;i<=n;i++) 90 if (f[i]==1) add(0,i,1),add(i,0,0); 91 for (i=1;i<=n;i++) 92 if (f[i]==s) add(n+i,2*n+1,1),add(2*n+1,n+i,0); 93 for (i=1;i<=n;i++) 94 add(i,n+i,1),add(n+i,i,0); 95 for (i=1;i<=n;i++) 96 for (j=1;j<=i-1;j++) 97 if (a[i]>=a[j]&&f[i]==f[j]+1) 98 add(n+j,i,1),add(i,n+j,0); 99 memcpy(edge2,edge,sizeof(edge));100 Dinic(0,2*n+1);101 cout< <