传送门：>Here<
题意：
给定正整数序列$x_1,...,x_n$
（1）计算其最长不下降子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。
（3）如果允许在取出的序列中多次使用$x_1$和$x_n$，则从给定序列中最多可取出多少个长度为$s$的不下降子序列。
思路分析
题意首先就很坑：注意第二问中的取出二字，意味着一个数字最多只能存在于一个LIS中。所以才会有第三问的假设
第一问
第一问很简单，直接暴力$O(n^2)$就好了
后面的两问需要借助于网络流。
第二问
直接解释原理不清晰也不易懂，先详细阐述如何建模过程：
首先原序列做LIS，其中$f[i]$表示以$a[i]$为结尾的LIS的最大长度。对序列的每一个数进行拆点，也就是分为$<X_i, Y_i>$。我们要让S到T的每一条路径都是一个LIS，因此若$f[i]=1$，则$X_i$的点连接源点（容量为1，后同），$f[i]=maxs$则$Y_i$连接汇点。其中对于每一个数字，连接有向边$(X_i, Y_i)$。并且在做LIS的过程中，若发现一对数字满足$a[j]<=a[i] 且 f[j]+1=f[i]$，则连有向边$(Y_j, X_i)$。最后做最大流即可
我们发现这道题又和二分图有一点类似。经过刚才这样的连边之后，任一S到T的路径都是一个LIS，并且容量为1保证了每个点不会被用两次（与二分图原理相同），因此最大流即为方案数
至于与二分图不同的地方我们发现，我们每个点本身连了边，最后LIS的边还是反过来加的。为什么要这么做呢？这是这道题最大的难点。
首先分析这种方法的正确性：经过现在这样的建图，Y部分称为了边的起点，而X成为了终点。设有一条边是$(Y_a, X_b)$，则其到达$X_b$以后会顺着自己的边到达$Y_b$，而后如果还存在一条边$(Y_b, X_c)$，它就会继续来到$Y_c$，以此类推最终到达T。其中$(X_i, Y_i)$起到了过渡作用，并且保证了每个点只走一次
然后来讲这种方法的必要性：为什么正着连边不行呢？原因在于我们源点与汇点的选择。想象一个序列$5,4,3,2,1$，按照目前这种方法自然会跑出最大流为5（每个点直接沿着自己的边走了）。然而如果正着连边自己反着连，那么将会跑出0——我们并没有给它一个跑出去的机会
第三问
第三问其实就是在第二问的基础上稍作了一些改动。$x_1和x_n$可以用无限次意味着可以去掉之前给这两个点只能用一次的束缚，因此只需要把源点到1，n到汇点的边的容量改为INF即可。注意由于现在起点是右侧点了，所以$(X_1,Y_1)$和$(X_n,Y_n)$的容量务必也要改成INF
Code
细节题。Dinic不要打错了不然完蛋
另外，再DFS的时候由于我们最初给S设的可增广量为INF，而容量也是INF，这就不太对了，因为源点还有可能连更多的边，INF就不够了。因此第三问的时候容量改为INF/10保险一点
/*By DennyQi*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define r read() #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) using namespace std; typedef long long ll; const int MAXN = 10010; const int MAXM = 10010; const int INF = 1061109567; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar(); return x * w; } int K,N,M,S,T,x,p,maxs; int first[MAXM*2],nxt[MAXM*2],to[MAXM*2],cap[MAXM*2],flow[MAXM*2],num_edge=-1; int level[MAXN],cur[MAXN]; queue <int> q; int a[MAXN],f[MAXN]; inline void add(int u, int v, int c, int f){ to[++num_edge] = v; cap[num_edge] = c; flow[num_edge] = f; nxt[num_edge] = first[u]; first[u] = num_edge; } inline bool BFS(){ memset(level, 0, sizeof(level)); while(!q.empty()) q.pop(); q.push(S); level[S] = 1; int u,v; while(!q.empty()){ u = q.front(); q.pop(); for(int i = first[u]; i!=-1; i = nxt[i]){ v = to[i]; if(!level[v] && cap[i]-flow[i]>0){ level[v] = level[u] + 1; q.push(v); } } } return level[T] != 0; } int DFS(int u, int a){ if(u == T || a == 0) return a; int ans = 0, _f,v; for(int& i = cur[u]; i != -1; i = nxt[i]){ v = to[i]; if(level[u]+1==level[v] && cap[i]-flow[i]>0){ _f = DFS(v, Min(a,cap[i]-flow[i])); ans += _f, a -= _f; flow[i] += _f, flow[i^1] -= _f; if(a == 0) break; } } return ans; } inline void Dinic(){ int ans = 0; while(BFS()){ for(int i = S; i <= T; ++i) cur[i] = first[i]; ans += DFS(S, INF*2); } printf("%d ", ans); } int main(){ N=r; memset(first, -1, sizeof(first)); S = 1, T = 2*N+2; for(int i = 1; i <= N; ++i){ a[i]=r; add(i<<1, i<<1|1, 1, 0); add(i<<1|1, i<<1, 0, 0); } maxs = 0; for(int i = 1; i <= N; ++i){ for(int j = 1; j < i; ++j){ if(a[j] <= a[i]){ f[i] = Max(f[i], f[j]); } } ++f[i]; maxs = Max(maxs, f[i]); for(int j = 1; j < i; ++j){ if(f[j]+1 == f[i] && a[j] <= a[i]){ add(j<<1|1, i<<1, 1, 0); add(i<<1, j<<1|1, 0, 0); } } } printf("%d ", maxs); for(int i = 1; i <= N; ++i){ if(f[i] == 1){ add(S, i<<1, 1, 0); add(i<<1, S, 0, 0); } if(f[i] == maxs){ add(i<<1|1, T, 1, 0); add(T, 1<<1|1, 0, 0); } } Dinic(); memset(flow, 0, sizeof(flow)); memset(first, -1, sizeof(first)); memset(nxt, 0, sizeof(nxt)); memset(f, 0, sizeof(f)); S = 1, T = 2*N+2; num_edge = -1; for(int i = 1; i <= N; ++i){ if(i == 1 || i == N){ add(i<<1, i<<1|1, INF/10, 0); add(i<<1|1, i<<1, 0, 0); continue; } add(i<<1, i<<1|1, 1, 0); add(i<<1|1, i<<1, 0, 0); } maxs = 0; for(int i = 1; i <= N; ++i){ for(int j = 1; j < i; ++j){ if(a[j] <= a[i]){ f[i] = Max(f[i], f[j]); } } ++f[i]; maxs = Max(maxs, f[i]); for(int j = 1; j < i; ++j){ if(f[j]+1 == f[i] && a[j] <= a[i]){ add(j<<1|1, i<<1, 1, 0); add(i<<1, j<<1|1, 0, 0); } } } for(int i = 1; i <= N; ++i){ if(f[i] == 1){ if(i == 1){ add(S, i<<1, INF/10, 0); add(i<<1, S, 0, 0); }else{ add(S, i<<1, 1, 0); add(i<<1, S, 0, 0); } } if(f[i] == maxs){ if(i == N){ add(i<<1|1, T, INF/10, 0); add(T, 1<<1|1, 0, 0); }else{ add(i<<1|1, T, 1, 0); add(T, 1<<1|1, 0, 0); }; } } Dinic(); return 0; }