题解：P15252 [NOSOI R1] Square Sequence

IkunTeddy · 2026-03-04 19:24:03 · 题解

简单题。

直接考虑子序列 dp。设 f_i 表示以 i 为某个颜色段开头的答案，s_i=\sum\limits_{k=2}^{i}(a_k-a_{k-1})^2，那么直接转移 f_i=\min\limits_{j=1}^{i-1}\{f_{j}+s_{i-1}-s_{j}+[j\ne 1](a_i-a_{j-1})^2\}。后面的式子直接用李超优化即可。

时间复杂度 O(n\log n)。

代码不放了。