«问题描述：
给定正整数序列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 的不下降子序列个数。
500n≤500
最长不下降子序列
这个题目第一问显然是LIS
第二问和第三问就转化成最大流。
转化过程（理解了好久）
第二问：
建图，先求出f数组，f[i]表示到第i为的最长的不下降子序列，
然后因为第二问每一个数只能用一次，所以就把一个点拆成一个入点一个出点。
建图就是让f[i]==1的和s连在一起，f[i]==ans的和t连在一起，然后中间如果有
a[i]>=a[j]&&i>j&&f[i]=f[j]+1 这样的话就把 j 的出点和 i 的入点连在一起，这个就是建图过程。
接下来说说为什么这么建图，
首先只考虑第二问，因为每一个点只能用一次，所以就把点拆开，并且权值为1 ,然后因为只有f[i]==1
才会和s点相连，设f[i]==1的个数为x，所以这个就说明最多只能有x个答案，在这个基础上再看有没有从这个
点出发可以到达f[i]==ans的。
接下来说说为什么会 a[i]>=a[j]&&i>j&&f[i]=f[j]+1 这个j的出点和i的入点连在一起。
这个必须是这样子写的，因为只有这个样子到f[i]==ans 的过程中把中间的数字标记一次，不让别的再跑了。
例如说样例： 3 6 2 5 这个ans=2 第二问答案有两组就是 3 6 和 2 5，
3和2都与源点连起来了，6和5 都和汇点连起来了，3也会和6 5 连起来，2就只会和6 连起来，
然后这个答案可以是3 5 或者2 6 和2 5 ，很显然后面的才是最大流。
然后第三问 首先你要看清楚题目，题目说的只是x1和xn可以用无数多次，
所以这个就只要改成 s 到1 和1到n+1 和 n到 n+n if(f[n]==ans) n到 t 这些边改成无数次然后就再跑一次。
因为f[i]==1所以从s到1很有可能会跑很多次，所以，这个既然x1可以用无数多次，则要设s到1和1到1+n为无数多次
如果f[n]!=ans 则说明这个点不会和t连在一起，所以就不能连n到t，但是n到n+n可以连无数多次，不过好像没什么用。
因为n是最后一个
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF = 2e9; int n, m, s, t, np = 1, p, mfl; int l[21][21], f[21], h[5005], cur[5005], tp[5005], q[50050]; struct rpg { int li, nx, ln; }a[50050]; void add(int ls, int nx, int ln) { a[++np] = (rpg) { h[ls], nx, ln }; h[ls] = np; a[++np] = (rpg) { h[nx], ls, 0 }; h[nx] = np; } int find(int x) { if (f[x] == x) return x; else return f[x] = find(f[x]); }void un(int a, int b) { int fa = find(a), fb = find(b); if (fa != fb) f[fa] = fb; } bool bfs(int ps) { memset(tp, 0, sizeof(tp)); int hd = 1, tl = 1; q[hd] = s; tp[s] = 1; while (hd <= tl) { int nw = q[hd++]; for (int i = h[nw]; i; i = a[i].li) { if (a[i].ln && !tp[a[i].nx]) { tp[a[i].nx] = tp[nw] + 1; q[++tl] = a[i].nx; } } }return tp[t]; } int dfs(int u, int maxn) { if (u == t || !maxn) return maxn; int sum = 0; for (int& i = cur[u]; i; i = a[i].li) { if (a[i].ln&&tp[a[i].nx] == tp[u] + 1) { int f = dfs(a[i].nx, min(maxn, a[i].ln)); if (f) { maxn -= f; sum += f; a[i].ln -= f; a[i ^ 1].ln += f; if (!maxn) break; } } }return sum; } void dnc(int ps) { while (bfs(ps)) { for (int i = 0; i <= ps; ++i) cur[i] = h[i]; while (int d = dfs(s, INF)) mfl += d; } } int main() { scanf("%d%d%d", &n, &l[0][0], &p); t = n + 1; for (int i = 1; i <= n + 1; ++i) f[i] = i; for (int i = 1; i <= l[0][0]; ++i) { scanf("%d%d", &l[0][i], &l[i][0]); for (int j = 1; j <= l[i][0]; ++j) { scanf("%d", &l[i][j]); if (l[i][j] == -1) l[i][j] = n + 1; if (j > 1) un(l[i][j], l[i][j - 1]); } }if (find(0) != find(n + 1)) { puts("0"); return 0; } for (int ti = 1;; ++ti) { for (int i = 0; i <= n; ++i) { add(i + (ti - 1)*(n + 2), i + ti * (n + 2), INF); }add(n + 1 + ti * (n + 2), n + 1 + (ti - 1)*(n + 2), INF); for (int i = 1; i <= l[0][0]; ++i) { int tmp = (ti - 1) % l[i][0] + 1; add(l[i][tmp] + (ti - 1)*(n + 2), l[i][ti%l[i][0] + 1] + ti * (n + 2), l[0][i]); } dnc((ti + 1)*(n + 2)); if (mfl >= p) { printf("%d\n", ti); return 0; } }return 0; }
原文：https://www.cnblogs.com/EchoZQN/p/10742750.html