Codeforces Round 666 Div1

比赛

最近场都好思维啊

A

巧妙构造，第一次取 n - 1 个，第二次取剩下 1 个，第三次取 n 个，前两次的目的就是把所有元素变成 n 的倍数

B

没有思路，将 a 排序，发现如果最大的比其他和都大那先手显然必胜。这个思路有点东西，继续挖掘发现两个人都尽量避免出现这种不均衡的局面，所有元素就会被取完，所以判断奇偶性就可以了。

C

1 <= r1 <= r2 <= r3 !!! 这个条件有点隐蔽，但是能简化一些分类讨论

所以要么 1 或 2 将所有的血量减一再用 1 打掉boss，要么 1 打掉小怪再 3 打掉boss

反复横跳。具体来说是跳一段回一步跳一段回一步…这样

dp, $f[i, 0/1]$ 表示最远到第 $i$ 关，前 $i - 1$ 关都消灭了，是否消灭了boss，0 代表消灭

初始 $f[1, 0] = a[1] r1 + r3$, $f[1, 1] = min(r1 (a[1] + 1), r2)$

$f[i, 0] = min(f[i - 1, 0] + d + (r1 a[i] + r3), f[i - 1, 1] + d + min(r1 (a[i] + 1), r2) + d + r1 + d + r1)$

$f[i, 1] = min(f[i - 1, 0] + d + min(r1 (a[i] + 1), r2), f[i - 1, 1] + d + min(r1 (a[i] + 1), r2) + d + r1 + d)$

答案是 $min(f[n, 0], f[n - 1, 1] + d + a[n] * r1 + r3 + d + r1)$