Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

题解「ROIR 2020」海报

posted on 2021-07-19 17:36:35 | under 动态DP |

Decription

「ROIR 2020」海报

Analysis

动态 DP 的入门题。

Part I 如何 DP?

由题目不难想到,设 $f_{i,j}$ 为选择考虑到第 $i$ 个点,最后 $j$ 个点必须选,选择的点最大美观度之和。

易得转移方程$$f_{i,j}=\begin{cases}f_{i-1,j-1}+a_i&j>0\\ \max\limits_{0\le k\le 3}(f_{i-1,k})&j=0\end{cases}$$

Part II 环?

对于环的问题,枚举前面有多少点和 1 一起被选,跑 4 次 DP 即可。

Part III 修改?

定义 Floyd 矩阵乘法$$c_{i,j}=\max_{1\le k\le r}\{a_{i,k}+b_{k,j}\}$$ 则转移方程可改写为$$\begin{pmatrix}f_{i-1,0}\\f_{i-1,1}\\f_{i-1,2}\\{f_{i-1,3}}\end{pmatrix}^{\text{T}}\begin{pmatrix}0&a_i&-\infty&-\infty\\0&-\infty&a_i&-\infty\\0&-\infty&-\infty&a_i\\0&-\infty&-\infty&-\infty\end{pmatrix}=\begin{pmatrix}f_{i,0}\\f_{i,1}\\f_{i,2}\\f_{i,3}\end{pmatrix}^{\text{T}}$$ 对每个 $i>4$,可 build 出一个转移矩阵,用线段树维护之即可。

Code

代码