题意
给定正整数序列(x_1 cdots x_n)。
-
计算其最长不下降子序列的长度(s)。如果每个元素只允许使用一次；
-
计算从给定的序列中最多可取出多少个长度为(s)的不下降子序列；
-
如果允许在取出的序列中多次使用(x_1)和(x_n)（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个不同的长度为(s)的不下降子序列。
令(a_1, a_2 cdots a_s)为构造(s)时所使用的下标，(b_1, b_2 cdots c_s)为构造(T)时所使用的下标。且(forall i in [1, s - 1])，都有(a_i < a_{i + 1}, b_i < b_{i + 1})。(S)和(T)不同，当且仅当(exists i in [1, s])，使得(a_i eq b_i)。
思路
本题的思路并不好想。因为数据范围比较小，第一问就很简单了，用(O(n^2))的DP就能解决了（而且为了后两问也需要用(O(n^2))的dp解决）。麻烦的是第二问和第三问。
PS：关于第二问具体的意思，结合第三问和样例理解，会发现是每个数字只能用一次（就是明摆着让人用网络流做呗╮(╯_╰)╭）。
PSS：第三问的意思是(x_1)和(x_n)可以重复使用，并不是有无限个(x_1)和(x_n)，和第二问中只能用一次相对。
网络流很难用于解决最长路径的问题，但是很适合解决路径数量这类问题。而解决路径问题，我们很常用的一种方法就是拆点。
我们看第二问和第三问，都是要我们求非降子序列的数量。因为题目仍然要求我们求最长非降子序列，我们很容易把目光放在最长上，但是再仔细一想，序列的长度其实已经固定了，而且再进一步思考，序列的起始元素和结束元素甚至都固定了。
我们先考虑第二问
为什么说序列的元素固定了呢？考虑第一问的dp，（假设(dp[i])表示以(i)结尾的最长非降子序列），起始的点(dp[i])一定为(1)，否则从该点起始一定得不到最长子序列。假设(ans)为第一问的到的答案，那么，只有(dp[i]=ans)的点才能作为结尾的点。
那么，我们会自然地想到，从源点向所有(dp[i]=1)的点连一条容量为(1)的边，从所有(dp[i] = ans)的点向汇点连接一条容量为(1)的边。（因为第二问中说过，每个数只能用一次，所以容量为(1)）。
然后，我们又遇到一个问题，点之间的边应该怎么连呢？我们仍然考虑dp的转移，显然：
我们的网络流也可以采取这样的转移：
对于(i)，我们枚举(j < i)，对于(j)满足(x[j] leqslant x[i])且(dp[i] == dp[j] + 1)，我们就加一条(j)连向(i)的边，表示我们可以从(j)点的状态转移到(i)。
到这里，我们已经基本解决了第二问了，不过还有一点小问题。我们要严格限制每个点只能用一次，所以我们稍微修改一下：
- 把每个点(i)拆成两个点(<x_i, y_i>)，然后在(x_i)和(y_i)之间连接一条容量为(1)的边；
- 上文提到的从源点(s)连向(i)的点改为连向(x_i)；
- 上文提到的从(i)连向汇点(t)的点改为从(y_i)连向(t)；
- 上文说到的点之间连边，从(j)连向(i)的边改为从(y_j)连向(x_i)
然后跑最大流就可以了。
半路总结
做到这里容易发现，整个第二问构图的过程其实几乎和第一问求dp的过程一模一样，只不过是把过程换到了图上而已。
再考虑第三问
想出来第二问，第三问就容易很多了。我们看第三问相对第二问的改动：(x_1)和(x_n)可以用无限次。
边的流量含义是什么？
第二问我们建立边的时候，为什么把流量设为(1)呢？就是为了确保这个点只能被用一次。
所以第三问，我们就把源点(s)连向(x_1)的边和(x_1)连向(y_1)的边容量都设置成(INF)，表示能用无穷多次，从(x_n)连向(y_n)的边容量也改成(INF)。
至于(y_n)连向汇点(t)的边，只有当(dp[n] = ans)时，我们才把(y_n)连向(t)的边容量改为(INF)，要不然(n)点本来就不是最长非降子序列的结尾，不能加上连向汇点的边。
最后，特殊注意一下(n = 1)这组数据。
代码
/**
* luogu P2766 https://www.luogu.com.cn/problem/P2766
* Dinic
**/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
const int maxn = 5005;
const int maxm = 550000;
const int s = 0;
const int t = maxn - 1;
const int INF = 0x3f3f3f3f;
using namespace std;
struct Edge {
int to, val, nxt;
}e[maxm];
int numedge, head[maxn], n, num[maxn], f[maxn], depth[maxn], a[maxn], ans, res;
inline void AddEdge(int from, int to, int val) {
e[numedge].to = to;
e[numedge].val = val;
e[numedge].nxt = head[from];
head[from] = numedge;
numedge++;
}
inline bool bfs() {
memset(depth, 0, sizeof(depth));
depth[s] = 1;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = e[i].nxt) {
int to = e[i].to;
if (!depth[to] && e[i].val > 0) {
depth[to] = depth[u] + 1;
q.push(to);
}
}
}
return depth[t] != 0;
}
int dfs(int u, int flow) {
if (u == t || flow == 0) return flow;
int res = 0;
for (int i = head[u]; ~i; i = e[i].nxt) {
int to = e[i].to;
if (depth[to] == depth[u] + 1 && e[i].val > 0) {
int di = dfs(to, min(flow, e[i].val));
if (di > 0) {
e[i].val -= di;
e[i ^ 1].val += di;
flow -= di;
res += di;
}
}
}
if (!res) depth[u] = 0;
return res;
}
void Dinic() {
while (bfs()) {
res += dfs(s, INF);
}
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
f[i] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[i] >= a[j]) {
f[i] = max(f[i], f[j] + 1);
}
}
ans = max(ans, f[i]);
}
printf("%d
", ans);
for (int i = 1; i <= n; i++) {
AddEdge(i, i + n, 1);
AddEdge(i + n, i, 0);
if (f[i] == 1) {
AddEdge(s, i, 1);
AddEdge(i, s, 0);
}
if (f[i] == ans) {
AddEdge(i + n, t, 1);
AddEdge(t, i + n, 0);
}
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[j] <= a[i] && f[i] == f[j] + 1) {
AddEdge(j + n, i, 1);
AddEdge(i, j + n, 0);
}
}
}
Dinic();
printf("%d
", res);
AddEdge(s, 1, INF);
AddEdge(1, s, 0);
AddEdge(1, 1 + n, INF);
AddEdge(1 + n, 1, 0);
AddEdge(n, n + n, INF);
AddEdge(n + n, n, 0);
if (f[n] == ans && n > 1) {
AddEdge(n + n, t, INF);
AddEdge(t, n + n, 0);
}
Dinic();
printf("%d
", res);
return 0;
}