给定 \(n\) 个数 \(a_1 \sim a_n\),这 \(n\) 个数围成一圈,\(a_i\) 与 \(a_{i - 1}, a_{i + 1}\) 相邻(\(a_1, a_n\) 相邻)。每次操作可以将某个数 \(+1/-1\),问至少经过几次操作能使每个数至少和它相邻的一个数相同?
\(45min\)。
首先不考虑环的情况。
令 \(dp_i\) 表示只考虑前 \(i\) 个数的情况下要满足要求的最小操作次数。
显然 \(dp_i\) 可以从任意 \(\le i - 2\) 的 \(j\) 转移过来,但是这显然会 TLE。实际上,\(dp_i\) 只可能从 \(dp_{i - 2}, dp_{i - 3}\) 转移过来,否则可以将 \(a_{i - 1}, a_i\) 变成一样的,剩下的变成一样的显然不劣。
在考虑 \(a_1\) 和 \(a_n\) 相邻这个问题,可以枚举 \(a_1, a_2, a_{n - 1}, a_n\) 这 \(4\) 个数是否有一些相邻(\(a_1, a_n | a_1, a_2, a_n | a_1, a_{n - 1}, a_n\) 三种)。然后强制令它们相同,做 \(4\) 次 DP 即可。
时间复杂度:\(O(n)\)。
本以为是断环成链,实际不可行。观察到 \(dp_i\) 只能从 \(dp_{i - 2}, dp_{i - 3}\) 转移就不难了。