题意分析

给定一个正整数序列 $x_1 \sim x_n$（非严格递增），要求：

1. 求最长递增子序列的长度 $s$。
2. 求最多能取出多少个互不相交的长度为 $s$ 的递增子序列。
3. 如果允许 $x_1$ 和 $x_n$ 被多个子序列重复使用，最多能取出多少个长度为 $s$ 的递增子序列。

第一部分：最长递增子序列长度 $s$

这是经典的 LIS 问题，可以用 $O(n^2)$ 的 DP 解决：

设 $dp[i]$ 表示以第 $i$ 个元素结尾的 LIS 长度： $ dp[i] = \max_{j < i, \, x_j \le x_i} \{ dp[j] \} + 1 $ 最终 $s = \max_{i=1}^n dp[i]$。

第二部分：最多不相交的长度为 $s$ 的 LIS

思路

我们要找多个长度为 $s$ 的 LIS，且它们不能共享元素（除了第三问的特殊情况）。

关键观察：

• 每个元素只能属于一个 LIS。
• 一个 LIS 是序列中 $dp$ 值依次为 $1, 2, \dots, s$ 的路径。

建模为网络流

1. 拆点：将每个位置 $i$ 拆成两个点 $i$ 和 $i'$，连一条容量为 $1$ 的边 $(i, i')$，表示每个位置只能用一次。
2. 建边：如果 $j < i$ 且 $x_j \le x_i$ 且 $dp[j] + 1 = dp[i]$，则从 $j'$ 向 $i$ 连一条容量为 $1$ 的边，表示可以接在后面形成 LIS。
3. 源点和汇点：
   • 从源点 $S$ 向所有 $dp[i] = 1$ 的 $i$ 点连容量为 $1$ 的边。
   • 从所有 $dp[i] = s$ 的 $i'$ 点向汇点 $T$ 连容量为 $1$ 的边。
4. 跑最大流，最大流的值就是最多能取出的不相交的长度为 $s$ 的 LIS 数量。

第三部分：允许重复使用 $x_1$ 和 $x_n$

修改容量

• 如果 $dp[1] = 1$，那么 $x_1$ 作为起点的边 $(S, 1)$ 容量改为 $\infty$。
• 如果 $dp[n] = s$，那么 $x_n$ 作为终点的边 $(n', T)$ 容量改为 $\infty$。
• 同时，$x_1$ 和 $x_n$ 对应的拆点边 $(1, 1')$ 和 $(n, n')$ 容量改为 $\infty$（如果它们可能被多次使用）。

这样，$x_1$ 和 $x_n$ 就可以被多个 LIS 重复使用。

样例验证

输入：

4
3 6 2 5

1. 计算 $dp$：

   • $x = [3, 6, 2, 5]$
   • $dp[1] = 1$
   • $dp[2] = 2$（3→6）
   • $dp[3] = 1$（2）
   • $dp[4] = 2$（3→5 或 2→5）
   • $s = 2$

2. 第二问：

   • 长度为 2 的 LIS 有：$[3,6]$, $[3,5]$, $[2,5]$
   • 但互不相交时最多选 2 个（如 $[3,6]$ 和 $[2,5]$）
   • 网络流最大流 = 2

3. 第三问：

   • 允许 $x_1=3$ 和 $x_4=5$ 重复使用
   • 可以取：$[3,6]$, $[3,5]$, $[2,5]$（都用到 3 或 5）
   • 网络流最大流 = 3

输出：

2
2
3

算法步骤总结

1. 读入 $n$ 和序列 $x$。
2. 用 DP 计算 $dp[i]$ 和 $s$。
3. 建图（拆点限制容量为 1）：
   • $(i, i')$ 容量 1
   • 若 $j < i, x_j \le x_i, dp[j]+1=dp[i]$，则 $(j', i)$ 容量 1
   • $S \to i$（$dp[i]=1$）容量 1
   • $i' \to T$（$dp[i]=s$）容量 1
4. 跑最大流得到第二问答案。
5. 修改与 $x_1$ 和 $x_n$ 相关的边容量为 $\infty$（如果它们分别是某个 LIS 的起点/终点）。
6. 再跑最大流得到第三问答案。
7. 输出 $s$、第二问答案、第三问答案。

复杂度分析

• $n \le 500$，$O(n^2)$ DP 可行。
• 网络流图节点数 $2n+2$，边数 $O(n^2)$，Dinic 算法 $O(V^2 E) \approx O(n^4)$ 在 $n=500$ 时可能稍大，但实际边数稀疏，可以接受。