在我的个人博客中阅读

题面

题意

给出一个长度为 $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

在我的个人博客中阅读

50 分：

暴力枚举即可

100 分：

设输入的序列为 $a_i$。容易发现，如果我们按原序列从左往右扫，扫到第 $i$ 个位置时，我们要考虑的是这一个位置要填什么以及 $a_i$ 要填到哪个位置上。

并且一共只有 5 种情况：

• $a_i$ 填到 $i$ 上；
• 拿一个比 $a_i$ 小的数填到 $i$ 上并且 $a_i$ 填到比 $i$ 小的位置上；
• 拿一个比 $a_i$ 小的数填到 $i$ 上并且 $a_i$ 填到比 $i$ 大的位置上；
• 拿一个比 $a_i$ 大的数填到 $i$ 上并且 $a_i$ 填到比 $i$ 大的位置上；
• 拿一个比 $a_i$ 大的数填到 $i$ 上并且 $a_i$ 填到比 $i$ 小的位置上

那么我们记 $f_{i,j,p}$ 表示现在填完第 $i$ 个数，比 $i$ 小（包括 $i$）的有 $j$ 个没填，并且算出来的价值为 $p$ 的方案数。假设我们现在考虑 $i+1$ 位填的数，分别考虑以上的五种情况。不过这里要注意的一点就是当这个位置填的数比它小时，是无法确定究竟是 $j$ 个当中的哪一个，因此这一部分的价值需要在之前填上 $j$ 这一位的时候就统计在答案中。

为了方便表述，借助标程的代码段进行解释（一些边界判断和取模略去）：

f[i+1][j][p+a[i+1]] += f[i][j][p];//第 i+1 位填 a[i+1]，不会产生新的未填项，并且产生新贡献为 a[i+1]
f[i+1][j-1][p] += f[i][j][p]*j*j;//第 i+1 位填比 a[i+1] 小的数并且 a[i+1] 填到比 i+1 小的位置上。减少一个未填项，产生新贡献为 0（这些贡献之前之前已经计算）
f[i+1][j][p+a[i+1]] += f[i][j][p]*j;//第 i+1 位填比 a[i+1] 小的数并且 a[i+1] 填到比 i+1 大的位置上。未填项数目不改变，产生新贡献为 a[i+1]（贡献来自 a[i+1] 填到的那位）
f[i+1][j+1][p+2*a[i+1]] += f[i][j][p];//第 i+1 位填比 a[i+1] 大的数并且 a[i+1] 填到比 i+1 大的位置上。未填项数目 +1，产生新贡献为 2*a[i+1]（贡献来自 i+1 位和 a[i+1] 填到的那位）
f[i+1][j][p+a[i+1]] += f[i][j][p]*j;//第 i+1 位填比 a[i+1] 大的数并且 a[i+1] 填到比 i+1 小的位置上。未填项数目不改变，产生新贡献为 a[i+1]（贡献来自 i+1 位）