Phantom Bird

外观

CSP-S 2024 T3 推式子

约 239 字小于 1 分钟

OI

2024-11-29

设 f(i,j)f(i,j) 为 11 ~ ii 格（jj ~ ii 同色）所得最大得分

f(i,i)=max⁡j=0i−1f(i−1,j+1)+Ai[Aj=Ai]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)+Ai[Ai=Ai−1]  (j<i)f(i,j)=f(i-1,j)+A_i[A_i=A_{i-1}]\ \ (j<i)

let Ei=Ai[Ai=Ai−1], Si=∑j=1iEi\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)+∑k=j+1iEi=f∗(j)+Si−Sjf(i,j)=f(j,j)+\sum_{k=j+1}^{i}E_i=f^*(j)+S_i-S_j

f∗(i)=f(i,i)=max⁡j=0i−1f(i−1,j+1)+Ai[Aj=Ai]=max⁡j=0i−1f∗(j+1)+Si−1−Sj+1+Ai[Aj=Ai]=Si−1+max⁡j=0i−1(g(j+1)+Ai[Aj=Ai])=Si−1+max⁡{max⁡j=1ig(j), Ai+max⁡j=0i−1[Aj=Ai]g(j+1)}\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*}

F(i)=max⁡j=1if(i,j)=max⁡j=1if∗(j)+Si−Sj=Si+max⁡j=1if∗(j)−Sj=Si+max⁡j=1ig(j)\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=1ig(j)\max_{j=1}^{i}g(j)

  • max⁡j=0i−1[Aj=Ai]g(j+1)\max_{j=0}^{i-1}[A_j=A_i]g(j+1)

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

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)