在我的个人博客中阅读

题面

题意

给出一个长度为 $n$ 的序列 $S$，$S$ 单调递增，问你有多少个序列 $T$ 以满足下列条件：

1. $T$ 是 $S$ 的一个排列。
2. $\sum_{i=1}^{n} \min(S_i,~T_i) = k$

$1 \le k \le 2500,~1 \le n \le 50,~1 \le S_i \le 50$

分析

我们发现 $k$ 的值非常小，所以我们考虑使用类似背包的方法考虑每一个 $S_i$ 和 $T_i$ 对总答案的贡献。

由于 $S$ 单调递增所以 $S$ 中的数互不相同，因此我们可以直接考虑分类讨论值 $S_i$ 在 $T$ 中的位置，令 $T_j = S_i$ 则：

1. 若 $j < i$，$S_j < S_i = T_j$，因此 $S_i$ 对答案产生 $0$ 的贡献。
2. 若 $j = i$，$S_j = S_i = T_j$，因此 $S_i$ 对答案产生 $S_i$ 的贡献。
3. 若 $j > i$，$S_j > S_i = T_j$，因此 $S_i$ 对答案产生 $S_i$ 的贡献。

计算答案的问题解决了，但是如何记录 $S_i$ 在 $T$ 中的位置？显然我们只关心 $j$ 与 $i$ 的大小关系，并不关心 $j$ 的具体值。因此我们只需要知道有多少中情况满足 $j < i$，$j = i$，$j > i$ 即可。

考虑使用 DP 解决此问题，$f[i][j][k]$ 表示已考虑 $S_1 \sim S_i$ 部分，$T_1 \sim T_i$ 中有 $j$ 个位置尚未确定值，且 $S_1 \sim S_i$ 部分对总答案的贡献为 $k$ 的方案数。转移时枚举 $j$ 与 $i$ 的大小关系和 $T_i$ 是否确定值即可。$T_i$ 不确定值时即意味 $T_i$ 将用 $> S_i$ 的数填充，$T_i$ 确定值时即意味 $T_i$ 将用 $\le S_i$ 的数填充。

具体转移见代码，建议手画几个图细心分析。

代码

View on GitHub