HS：这题考察基本功（诶自然数拆分怎么做我看看）。

一个基础的观察：对于物品 $i$，当 $i\ge\sqrt{n}$ 时物品不可能取完，所以这部分是一个完全背包。

问题分成了两部分，设 $B=\lceil\sqrt{n}\rceil$，令 $F_i$ 表示只用 $1\sim B$ 这些物品体积为 $i$ 的方案数，$G_i$ 表示只用 $B+1\sim n$ 这些物品体积为 $i$ 的方案数，最后对 $F,G$ 卷一下即可。

对于 $F_i$：就是一个裸的完全背包，单调队列可以 $O(n\sqrt{n})$，但因为计数背包是可以退的，所以直接记录前缀和就可以 $O(n\sqrt{n})$。

对于 $G_i$：选择的物品不超过 $\sqrt{n}$ 个，考虑设 $g_{i,j}$ 表示这部分选择 $i$ 个物品体积和为 $j$ 的方案数，为了避免记重强制选择的物品体积单调递减。

问题变成了对一个单调递减，和为 $j$，最小数超过 $\sqrt{n}$ 的序列计数。如何刻画单调递减，经典做法是维护一个空数列，每次全局加一，或者在末尾加入一个最小元素，因此可以得出转移式 $g_{i,j}=g_{i,j-i}+g_{i-1,j-B-1}$。状态数是 $O(n\sqrt{n})$，转移是 $O(1)$ 的。

综上，在 $O(n\sqrt{n})$ 的时间复杂度内解决了本题。

比较经典的计数题。

考虑 $\sum a_i^2$ 的组合意义，等价于枚举两个取球方案，且两个方案最终取得的序列相同的方案数。

设 $f_{i,j,k}$ 表示取了 $i$ 个球，枚举的两个方案中，第一个方案在上侧取了 $j$ 个球，在下册取了 $k$ 个球。且目前两种取球的方案得到的序列一样的方案数。

枚举第 $i+1$ 个球取上面还是下面，转移即可，滚动数组优化空间，即可做到 $O(n^3+n^2m))$ 的时间复杂度和 $O(n^2)$ 的空间复杂度。

$1 \le n \le 10 ^ 5$

这个题要求的是第 $i$ 发导弹不能高于第 $i - 1$ 发，也就是说，我们的导弹的高度是单调不升的，我们最多能拦截的导弹怎么算呢？最少用几套系统拦截呢？

对于第一问来说，我们将视角反转过来，看从末尾开始，每次导弹的高度都要大于等于上一次的，最多能打几个，那么这就是一个简单的 LIS 问题，那么我们求的就是非严格上升的最长子序列。

对于这类问题我们采用的方式常见的就是 $\mathcal{O}(n ^ 2)$ 的 DP，但是这个题的复杂度不允许，我们用另一种形式，我们定义 $f_i$ 表示长度为 $i$ 结尾的这样的上升子序列，结尾最短的值，那么我们发现这个值在 $f$ 中一定是单调的，我们考虑维护这个 $f$ 数组。

如果当前的 $a_i > f_t$，那么说明当前的 $a_i$ 只能接到 $f$ 的后面，无法对之前的造成任何有益的贡献。

如果当前的 $a_i \le f_t$，那么说明当前的 $a_i$ 虽然不能接到 $f$ 的后面，但是可以对之前更短的 $f$ 产生一个更优的贡献，我们只需要找到第一个大于 $a_i$ 的位置的 $f_j$，直接 $f_j \to a_i$ 即可。

然后对于第二问来说，这是一个很著名的定理，叫做 **Dilworth 定理**，这个定理的内容是这样的：

对于一个偏序集 $S$ 上的偏序 $\preceq$，称 $S$ 的全序子集为 **链**。若 $S$ 的子集 $T$ 中任意两个不同的元素均不可比则我们称 $T$ 为反链。

说人话就是，现在有一个全集 $S$，从中选出若干个元素，组成一个集合，这个集合按一种特殊的偏序的关系，则这个集合 $S$ 中的任意两个元素都能进行比较，则这个子集称为**链**。若有个子集 $T$，对于这个集合中的任意选出的两个元素，都无法按照这种偏序关系比较，那么称这个子集 $T$ 为**反链**。

需要注意的是这个偏序关系 $\preceq$ 来说，其可能是一种比较方式，就是钦定的一种规则，例如，当 $a \le b$ 时我们称其为可比，那么我们拿出来的如果是 $a > b$ 就是不可比。

我们设 $(S, \preceq)$ 为一个有限偏序集，则：

- 最小链覆盖数 = 最大反链长度

- 最小反链覆盖数 = 最大链长度

那我们这个题就可以直接做了，我们对于 $\ge$ 的偏序关系来说，其反就是 $<$，就是严格的小于，那么我们求严格最长上升的长度就是答案。

$1 \le n \le 3.5 \times 10 ^ 4, 1 \le a_i \le 10 ^ 5$

题面很简约，长度为 $n$ 的整数序列 $a$，我们要保证这个东西在修改完之后是严格单调递增的，第一问问我们最少改变的数的个数。

很朴素的思路是我们先求出 LIS，再直接用 $n - l$ 就是答案，但是这样是错的，我们看这个样例：

4
1 2 2 3

对于这个来说，我们的 LIS 选出的长度显然是 $3$，就是 $\{ 1, 2, 3\}$，这样的话我们的代码误以为我们只需要对 $2$ 修改即可，但是实际上并非这样，我们的 $2$ 无法修改为 $2 \sim 3$ 中间的任何 $Z$。

那怎么办呢？我们选择 $a_i$ 和 $a_j$ 作为一对上升的序列中的一部分的条件不止 $a_i < a_j$，我们发现其还满足 $a_j - a_i \ge j - i$，我们对其移项得到 $a_j - j \ge a_i - i$，那么我们直接重标号，定义数组 $b$，使得 $b_i = a_i - i$，那么我们只需要对于这个 $b$ 求 LIS 即可，答案就是 $n - l$。

对于第二问，其要求我们在第一问的基础上，对选出的这最少的进行修改，使得修改的绝对值之和最小。

我们要把 $a$ 变成严格上升的和 $b$ 变成单调不降的修改的答案应当是一样的，我们这里做一个简单证明，对于 $a_i$ 和 $a_{i + 1}$ 来说，我们要求的是 $a_i < a_{i + 1} \rightarrow a_i + 1 \le a_{i + 1}$，而我们的 $b_{i} = a_i - i$，那么我们的 $b_i - i \le b_{i + 1} - i - 1 \rightarrow a_i + 1 \le a_{i + 1}$。好的我们已经证明了问题是等价的，那么我们去解决 $b$ 的单调不降问题即可。

接下来我们考虑这样的问题，定义集合 $T \in S$，$T$ 是其全集 $S$ 的 $\preceq$，我们现在要解决的是 $A \notin T$ 的这些应该把题面放到哪里呢？

我们考虑假设我们已经考虑好前 $i$ 个元素的答案是 $f_i$，我们现在要求你从这个 $i$ 转移到下一个 LIS 加 $1$ 的位置怎么转移。我们现在问题在于中间的 $[i + 1, j - 1]$ 的区间的点全是要么 $< b_i$ 的，要么是落在 $> b_j$ 的，如下图：

我们应当如何调整中间的 $b$ 呢？我们要求 $b$ 单调不降，那么我们至少是 $b_i \le b_{i + 1}$，我们至少需要让这些东西全落在黄色的部分。

那么如何做到最小呢，我们显然是尽可能的使其贴近边框，我们称以一个点 $k \in [i + 1, j - 1]$ 的部分，我们使得 $[i + 1, k]$ 的部分直接移动到下边框上，$[k + 1, j - 1]$ 的部分我们直接移动到上边框上，这个时候一定是有最优解的。如下图：

如何证明这个解是最优解呢，我们考虑这样的折中方案（毕竟人脑觉得很优），如下图：

我们定义这样的紫色平台中的从上方降下来的为 $Y$，从下方升上来的为 $X$，那么分为以下三中情况：

1. $X > Y$

   那么我们说，如果将所有紫色平台全部降下去，由于 $X > Y$ 的缘故，最终的 $\Delta > 0$，我们刚刚的方案是优的。

2. $X < Y$

   那么这种情况是和上面的是对称的，我们将所有平台升上去，最终的 $\Delta > 0$，所以也优。

3. $X = Y$

   这种情况在中间和两边共享最优方案。

因此，我们证明了刚刚的划分方式一定包含最优解。

那么最终的实现还是不是很好实现的，我们将上述的内容转成式子，可以得到下式：

$$dp_j = \min \{ dp_j, dp_i + \sum_{p = i + 1} ^ k |b_p - b_i| + \sum_{p = k + 1} ^ {j - 1} |b_p - b_j| \}$$

我们注意到这个式子的两个 $\sum$ 可以在每一轮直接用前后缀和预处理出来，可是你的 $i, j$ 的枚举就已经达到了 $\mathcal{O}(n ^ 2)$，怎么办呢？

我们发现很多地方的枚举是无效的，我们需要使得 $j$ 的位置的结尾的 LIS 长度恰好为 $i$ 位置为结尾的 LIS 的长度 $+1$，那么我们直接开一个 vector 来记录长度为 $i$ 的下标的下标集合，这样我们枚举 $j$，只需要从 $l_j - 1$ 的长度的下标的地方转移，这是一个很大的优化。因为随机数据下 LIS 长度的期望是 $\mathcal{O}(\sqrt{n})$，那么实际上我们最终的复杂度期望在 $\mathcal{O}(n \sqrt{n})$ 左右，对于 $3.5 \times 10 ^ 4$ 的数据也是轻松通过。

$1 \le n \le 1000, 1 \le m \le 200, 1 \le k \le m$

我们发现 $A$ 的 $k$ 个子串拼接的 $S$，且 $S = B$ 的方案数。

我们定义这样的方案，我们发现这个子串的拼接方式是这样的：

1. 直接接到上次的子串后面

2. 单开一个新的子串

我们定义这样的状态，$f[i][j][k]$ 表示必须选择 $i$ 这个点，已经选择出来了 $k$ 个子串，能与 $B$ 的前 $j$ 个字符相匹配，定义 $g[i][j][k]$ 表示选或不选 $i$ 这个位置，剩下和 $f$ 的定义一样的方案数。

那么我们的转移是这样的：

- 当 $A_i = B_j$ 的时候

 那么 $f[i][j][k] = (f[i - 1][j - 1][k] + g[i - 1][j - 1][k - 1])$，这个东西就是，要么你拼接在后面，要么你单开一个，造成新的 $k$ 的贡献。我们的 $g[i][j][k] = (g[i][j][k] + f[i - 1][j][k])$，这个东西就是你不选 $i$ 的和上一次的。

- 当 $A_i \ne B_j$ 的时候

 那么我们的 $f[i][j][k] = 0$，我们的 $g[i][j][k] = g[i- 1][j][k]$。

但是我发现此时的空间超限，我们发现每次的 $i$ 只从 $i - 1$ 转移，于是我们很愉快的滚动数组优化一下即可。或者倒序枚举。