2020 Petrozavodsk Winter Camp Day 5 F
Problem F. The Halfwitters
Statement
给定长度 $n$，给定 $a, b, c$，给 $d$ 次询问。每次询问是一个长度为 $n$ 的排列，你可以对这个票列做三种操作：
花费 $a$ 代价，交换相邻的两个数；
花费 $b$ 代价，翻转这个排列；
花费 $c$ 代价，shuffle 这个排列。
对于每次询问，你需要求出，在最优的操作策略下，把排列排成升序所需的最小期望代价。有 $z$ 组测试数据。
$2 \leq n \leq 16$, $1 \leq a, b, c \leq 1000$, $1 \leq d \leq 10000$
$\sum d \leq 10^5$
Solution
考虑只有第一种操作，我们不难发现，总代价只跟逆序对数 $inv$ 有关。
$$
ans_{1}(inv) = inv \cdot a
$$
考虑加上第二种操作，我们不难发现，先翻转一下再只进行以上操作可能会更快！
$$
ans_{12}(inv) = \min(ans_{1}(inv), b + (\frac{n(n-1)}{2} - inv) \cdot a)
$$
考虑加上第三种操作，我们不难发现，先 shuffle 一下再只进行以上操作可能会更快！我们令 shuffle 后代价的期望是 $x$。
$$
ans_{123} = \min(ans_{12}(inv), x + c)
$$
那么，怎么求 $x$ 呢？记逆序对数为 $inv$ 的排列有 $L_{inv}$ 个，如果我们只能进行一次 shuffle 操作，那么显然
$$
x = \frac
{\sum_{inv = 0}^{\frac{n(n-1)}{2}} L_{inv} \cdot ans_{12}(inv)}
{n!}
$$
但是实际上，有可能 shuffle 一次之后我们不满意，那就有可能继续 shuffle。所以我们只好列一个方程来计算 $x$。
我们知道，shuffle 后有一部分满意的情况（即 $ans_{12}(inv) \leq x + c$），其中每种情况的代价是 $ans_{12}(inv)$；也有一部分不满意的情况（即 $ans_{12}(inv) > x + c$），其中每种情况的代价是 $x + c$。于是我们可以把上面那个错误的式子改成这样一个正确的式子：
$$
x = \frac
{\sum_{ans_{12}(inv) \leq x + c} L_{inv} \cdot ans_{12}(inv) +
\sum_{ans_{12}(inv) > x + c} L_{inv} \cdot (x + c) }
{n!}
$$
为了方便计算这个东西，我们变换一下下标。令 $id$ 是一个排列且满足 $ans_{12}(id_i)$ 关于 $i$ 单增（用排序就可以实现），那么显然会有一个分界点 $k$ 使得
$$
x = \frac
{\sum_{i = 0}^{k} L_{id_i} \cdot ans_{12}(id_i) +
\sum_{i = k + 1}^{\frac{n(n-1)}{2}} L_{id_i} \cdot (x + c) }
{n!}
$$
把 $x$ 挪到一边
$$
x = \frac
{\sum_{i = 0}^{k} L_{id_i} \cdot ans_{12}(id_i) +
\sum_{i = k + 1}^{\frac{n(n-1)}{2}} L_{id_i} \cdot c }
{n! - \sum_{i = k + 1}^{\frac{n(n-1)}{2}} L_{id_i}}
$$
考虑到 $n! = \sum_{i=0}^{\frac{n(n-1)}{2}} L_i$，我们可以修改得好看一点
$$
x + c = \frac
{\sum_{i = 0}^{k} L_{id_i} \cdot ans_{12}(id_i) + n! \cdot c}
{\sum_{i = 0}^{k} L_{id_i}}
$$
这个方程有两个未知量 $x$ 和 $k$，但是我们不难发现它们必定满足 $ans_{12}(k) \leq x + c \leq ans_{12}(k + 1)$。然后我们预处理一下前缀和，枚举 $k$ 找合法解就可以辣！
$L_i$ 不会求的话，可以参考 [HAOI2009] 逆序对数列 。
Code
1 |
|