HTR003D 序列

发布于 2021-08-27  1.1k 次阅读


题面

题意

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


我缓慢吐出一串啊吧啊吧并不再想说话