Codeforces Round #809 (Div. 2)总结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16500199.html

比赛地址

排名：324
AC：4 / 6

显然对于每一步，如果靠前没选就选靠前的，否则选靠后的

加入两个相同数字之间可以连起来，它们相隔的个数必然是偶数，然后模拟即可

对于奇数的情况显然，每个分别计算即可

对于偶数的情况我采取dp，去掉左右两个，中间两个为1组，设 $dp_{i,0/1}$ 表示在第 $i$ 组放在前一个/后一个的最小代价， $cal(x)$ 表示第 $x$ 个的代价，则

$\Large dp_{i,0}=dp_{i-1,0}+cal(x)\\\Large dp_{i,1}=\min(dp_{i-1,0},dp_{i-1,1})+cal(x+1)$

答案即为 $\min(dp_{n,0},dp_{n,1})$ （ $n$ 要变换一下）

设 $dp_{i,j}$ 表示前 $i$ 个数最小值为 $j$ 时最大值的最小，如果 $j$ 不存在就为 $\inf$

而如何求当前第一个大于等于 $j$ 的值呢？二分。

然后就从上一步推过来即可。时间复杂度 $O(n^2\log n)$

赛后看题解发现不用二分，可以直接 $O(1)$ 求出，所以可以优化个 $\log$

虽然AC没实现突破，但较为顺利

开场3min过A，B盲猜个结论16min时过

C就是纯模拟，偶数一开始以为只有两种情况，后来过不了样例改成dp，26min时过

D1想了一会就想到dp，但一直调不出，61min时才过

然后D2和E想了一会想不出就弃了