VP: AtCoder Beginner Contest 404

## A

不解释，根本没做

## B

不解释，根本没做

## C

不解释，根本没做

## D

很难绷，输入看错了，然后也没有看见每个动物至少访问两边。早上不太清醒，调了一个小时。遂过。

爆搜即可。

[Submission](https://atcoder.jp/contests/abc404/submissions/65796720)

## E

首先容易想到，只要是要移动 beans 肯定是一次性移动到当前点能移动的最左端，也就是 $i - c_i$ 。否则答案必然更劣。

考虑当前 $a_i \neq 0$ 的位置是 $cur$，上一个 $a_i \neq 0$ 的位置是 $pre$，当前需要从 $pre$ 把豆子转移到 $cur$ 来。

假如 $pre \in [cur-c_{cur}, cur]$ 的话，那么直接操作数 $+1$ 直接到位了。

否则的话，我们需要通过其他的点作为“中介”。设 $f_i$ 表示走到 $f_i$ 所需要的最少步数，考虑从 $j \in [cur, pre)$ 从后往前转移：
$$
f_k = \min_{j} \{f_j\} + 1
$$
其中 $k \in \max [\{pre, j - c_j\}, j)$

之后给操作数加上 $f_{pre}$ 即可。

[Submission](https://atcoder.jp/contests/abc404/submissions/65797616)

## F

感觉很难。本来 dp 就是自己从高中以来就菜的一个专题。现在更是完全不会。

首先想到的状态是设 $f_{i,j}$ 表示第i轮覆盖了 $j$ 次的概率，转移为 $f_{i,j} = \frac{1}{n} \sum_{paritition C, t = 1}^{i - 1} f_{t,c} $

这里是看错题了，题目要分配每一轮按的按键，而不是一个按键按 $C$ 次。

所以这样的话，应该中间要一个额外的 DP 数组去枚举在本轮中分到恰好 $x$ 次按压的那个键的贡献。

而且，假如是设前 $i$ 轮共中了 $j$ 次，那么 $f_{i,j}$ 的转移大概是：
$$
f_{i,j} = \sum_{c=0}^{M} f_{i-1,j-c} \times P(A)
$$
其中记事件 $A$ 为第 $i$ 轮命中了 $c$ 次。

这里的问题还是在假设每一轮按键的方案是一样的（实际上是不一样的）。同时，$P(A)$ 实际上是 $P(c|\text{状态}(i-1,j-c))$ 。所以是一个条件概率，表示从状态 $(i-1,j-c)$ 的条件下（从这个状态转移过来），恰好是 $c$ 次。然而，**按压策略是通过“未来收益”（即剩余轮次的胜率）来优化的。** 然而，一旦想找最优，这里就不能是简单用一个式子计算，相当于需要再 dp 一次变成一个最大化期望。当然，也可以枚举所有可能的转移过来的状态。

重新设 $f_{t,k}$ 表示当前是第 $t$ 轮，到这一轮开始时已经累计按中了winning按钮 $k$ 次，且后续能**最大化**获胜的概率

考虑转移。首先每一轮的排列都在变，显然 $P(\text{winning button} = i) = \frac{1}{N}$， 那么假设 $\text{winning button} = i$

1. 假设 $i$ 我们按了 $c$ 次，那么下一状态就是 $(t + 1, k + c)$ ，也就是胜率是 $f_{t+1,k+c}$
2. 对于其他的非 winning button，无论按多少次，都不会改变累计数，下一状态依然是 $f_{t+1,k}$

因此，
$$
f_{t,k} = \max_{\{c_1, \dots, c_N\}: \sum c_i = M} \frac{1}{N} \sum_{i=1}^{N} [\text{winning button = i, pressed } c \text{ times}] \times f_{t+1,k+c_i}
$$
其中 $[]$ 内的式子，可以直接爆搜枚举所有状态。也可以按照如下方式 dp。

1. 先选在这一轮里，恰好有 $n$ 个不同的位置被按了 $>0$ 次， 剩下的 $N - n $ 个位置按了 $0$ 次
2. 再钦定这 $n$ 个按了的位置上按的次数，使其按压次数的和为 $M$。最后取最大 $\sum_{j=1}^{n} f_{t+1,k+c_j}$ 的方案

设 $g_{i,s}$ 为：
$$
g_{i,s} = \max_{\sum c_i = s, \forall c_i \geq 1} \sum_{j=1}^{i} f_{t+1,j+c_i}
$$
这里要注意到，$g$ 算的都是被按过的，所以 $\forall c_i \geq 1$ 是必须的。

考虑转移：
$$
g_{i,s} = \max_{x=1,\dots,s-(i-1)} (g_{i-1,s-x} + f_{t+1,k+x})
$$
最后算一下:
$$
\frac{1}{N} \max \{g[n][M] + (N - n) \times f_{t+1,k}\}
$$
[Submission](https://atcoder.jp/contests/abc404/submissions/65805152)

## G

差分约束裸题。不解释

[Submission](https://atcoder.jp/contests/abc404/submissions/65813636)

## A

不解释，根本没做

## B

不解释，根本没做

## C

不解释，根本没做

## D

很难绷，输入看错了，然后也没有看见每个动物至少访问两边。早上不太清醒，调了一个小时。遂过。

爆搜即可。