排名: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想了一会想不出就弃了