CodeForces-2153D Not Alone
tag: 结论题，一维线性 DP
给定一个环形序列 \(b\)，长度为 \(m\)，每次操作可以将一个数加一或减一。
问最少需要多少次操作，可以使序列 \(b\) 中每一个元素至少与一个相邻元素相等。
环形序列是指：除了 \(b_i\) 和 \(b_{i+1}\)（\(1\le i<m\)）相邻，\(b_m\) 和 \(b_1\) 也相邻。\(\sum m\le2\cdot10^5\)。
感谢 dbxxx 的帮助。
相当于将序列分组，每组中至少有两个数，执行操作使每组中所有数相等。
先考虑非环形的序列，即忽略 \(b_m\) 和 \(b_1\) 相邻的情况。
结论：每组只包含两个或三个数，可以使答案最优。
感性证明：首先，若已经分组，那么经典的结论是，将这一组中所有数变为它们的中位数，所需操作最少。
对于连续的四个数，从左到右分别为 \(a,b,c,d\)，画图理解：
显然右侧的更优（至少不劣）。交换 \(a,b\) 或交换 \(c,d\) 或交换 \((a,b),(c,d)\) 都不影响结果，因此上面已经考虑到了所有情况。
对于连续的五个数，也是同样的道理，但这时应该分为 \((a,b,c),(d,e)\) 还是 \((a,b),(c,d,e)\) 是不确定的，需要分类讨论。
考虑 DP，设 \(f(i)\) 表示将 \(b_1,\cdots,b_i\) 变为合法序列的代价。那么讨论 \((i,i-1)\) 或 \((i,i-1,i-2)\) 为一组，故
其中极差 \(R(l,r)=\max\{b_l,\cdots,b_r\}-\min\{b_l,\cdots,b_r\}\)。
现在考虑环形序列的情况。环与链的区别只是在于，需要多考虑 \((b_m,b_1),(b_{m-1},b_m,b_1),(b_m,b_1,b_2)\) 这三种分组。
故只需要对 \(b'=(b_2,\cdots,b_{m-1},b_m,b_1)\) 和 \(b''=(b_3,\cdots,b_{m-1},b_m,b_1,b_2)\) 再跑两遍即可。
Submission #343107772 - Codeforces