好不稳定的 blog，不过至少比我有希望。
不希望我辛辛苦苦打的 LATEX 被吃掉，因此请移步这里
鞠躬
好吧链接打不开，需要翻墙。
备份了一份在那边，当作留给自己的遗产
不行了不行了选题风格已经日渐走向猎奇的方向了
我真的打不下去了救救我救救我
（昏倒
再贴一贴神秘题单链接
[T1]
非常好的动态DP，但是我之前不知道。
只考虑线性情况时，我们可以写出一个朴素的方程：
设 f_{i, j} 表示以 i 为结尾，目前末尾连续选择了 j 个数，显然地， j \leq 3
转移是好写的，有：
$f{i, 0} = \max{j = 0}^{3} f_{i – 1, j}$
$f{i, j} = f{i – 1,j – 1} + w_i (j > 0)$
我们并不希望破环成链，怎么办呢？
答案是做四次，相当于强制指定一个点不选，而连续的四个必定是有一个不选的，因此这样做是正确的
接下来考虑优化这个东西，然后就 莫名其妙 想到了动态DP所使用的广义矩阵乘法。
广义矩阵乘法满足结合律的条件是：
- $\bigoplus$ 运算满足交换律。
- $\bigotimes$ 运算满足交换律和结合律。
- $\bigotimes$ 对 $\bigoplus$ 存在分配律。
对于本题，\bigotimes 是 \max， \bigoplus 是 +，发现是满足的（\max(a,b) + c = \max(a + c, b + c)）
于是可以开开心心把自己写的矩阵乘法稍作修改，就能拿来当另一个板子了。
提供半个板子：