Decription
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 出一个转移矩阵，用线段树维护之即可。