查看源代码：
CSP-S-2024-T3.md

---
title: CSP-S 2024 T3 推式子
createTime: 2024/11/29
categories:
    - IT
tags:
    - OI
---

设 $f(i,j)$ 为 $1$ ~ $i$ 格（$j$ ~ $i$ 同色）所得最大得分

$$f(i,i)=\max_{j=0}^{i-1} f(i-1,j+1)+A_i[A_j=A_i]$$
$$f(i,j)=f(i-1,j)+A_i[A_i=A_{i-1}]\ \ (j<i)$$

---

$$\text{let } E_i=A_i[A_i=A_{i-1}],\ S_i=\sum_{j=1}^i E_i$$
$$f(i,j)=f(j,j)+\sum_{k=j+1}^{i}E_i=f^*(j)+S_i-S_j$$

---

$$
\begin{align*}
f^*(i)=f(i,i)&=\max_{j=0}^{i-1} f(i-1,j+1)+A_i[A_j=A_i] \\
&=\max_{j=0}^{i-1}f^*(j+1)+S_{i-1}-S_{j+1}+A_i[A_j=A_i] \\
&=S_{i-1}+\max_{j=0}^{i-1}\left(g(j+1)+A_i[A_j=A_i]\right) \\
&=S_{i-1}+\max\left\{\max_{j=1}^{i}g(j),\ A_i+\max_{j=0}^{i-1}[A_j=A_i]g(j+1)\right\}
\end{align*}
$$

---


$$
\begin{align*}
F(i)&=\max_{j=1}^{i}f(i,j) \\
&=\max_{j=1}^{i}f^*(j)+S_i-S_j \\
&=S_i+\max_{j=1}^{i}f^*(j)-S_j \\
&=S_i+\max_{j=1}^{i}g(j)
\end{align*}
$$

---

需要维护：
- $\max_{j=1}^{i}g(j)$

- $\max_{j=0}^{i-1}[A_j=A_i]g(j+1)$

后者离散化后开数组存即可。