color

_32_qwq · 2024-10-27 21:09:26 · 题解

直接大力线性 dp，经典模型是直接定义 f_i 表示 i 的答案，然后枚举前面的 j 进行转移。

放到本题中，j 就是 i 前面第一个和 i 同色/异色的位置，如果是异色的话，j 的贡献不是很好算，直接在状态上做手脚，把 f_i 的定义改成钦定 i 和 i+1 颜色不同时的答案。

转移就看 i 和 i-1 的颜色关系，不妨令 i 和 i-1 同色，异色同理。

枚举 j 表示 [1,i-2] 中最后一个和 i 异色的位置，那么 j 和 i+1 颜色相同，有转移 f_i\gets\max\{f_i,f_j+\sum\limits_{k=j+1}^{i-1}[a_k=a_{k+1}]a_k+[a_j=a_{i+1}]a_j\}。

令 s_i=\sum\limits_{j=1}^{i-1}[a_j=a_{j+1}]a_j，有转移 f_i\gets\max\{f_i,f_j+s_{i-1}-s_j+[a_j=a_{i+1}]a_j\}。

这时已经容易想到讨论 a_j 和 a_{i+1} 的关系了。

若 a_j=a_{i+1}，那么容易想到令 j 为 [1,i-2] 最后一次出现 a_j 的位置一定不劣，这种情况单独算即可。

若 a_j\ne a_{i+1}，其实可以把 a_j=a_{i+1} 的情况放一起算，因为少加上了 a_j 一定不优，就是 f_i\gets\max\{f_i,f_j+s_{i-1}-s_j\}，用前缀 \max 维护一下即可。