在你得出差分序列单谷的性质之后,有这样一个dp:
强行钦定差分序列最小值处的 a=0 ,然后变成从小到大枚举差分值,往左或往右放的问题。
设 f[l][r][s] 表示往左放的差分值和是 l ,往右放的差分值和是 r ,目前已有的 ai 和为 s 的情况下,∑ai2 最小是多少。
理论上这个 s 最大可能到 O(nm) ( m 是 ai 的最大值),但这题的评论区里已经有人说了这一维不太可能跑满,所以你大概卡一个上界(比如常数倍的 m )就行了。
但如果你不知道这个上界到底开多少才稳妥,还有这么一个卡时做法:
枚举最终所有数的和 s ,然后在dp时直接省略 s 这一维, dp[l][r] 表示左边差分值的和 l 右边差分值的和 r 的情况下, ∑(nai−s)2 最小是多少。
注意看上去这个式子因为没有在dp里控制真正的 ∑ai 是多少,但是结果却是对的,因为如果你把方差的计算公式 ∑(ai−a)2/n 中的 a 换成别的值的话只会让算出来的方差偏大,所有的东西求个最小值之后就只剩下最优解里正确的 s 算出来的方差了。
这样一来你就可以枚举 s 然后卡时,单次dp是 O(m2) 的。
目前我们没有任何人能卡掉这个做法(盲猜CCF也卡不掉),所以我们猜最终答案中这个 s 可能就是最多 O(m) 级别的,但我们也不会证明。
所以有谁能证明这个结论或构造能卡掉这个卡时做法的数据吗qwq