序列 DP

(1) LOJ P507 接竹竿

• 有 \(n\) 张牌排成一排，每张牌有属性 \((c_i, v_i)\)。保证 \(c_i \le k\)。

  每次操作选择两张牌 \(l, r\) 满足 \(c_l = c_r\)，删除 \(l \sim r\) 中的所有牌，并获得 \(\sum_{i=l}^rv_i\) 的收益。

  求最大的收益。

• \(n, k \le 10^6\)。

设状态 \(f_i\) 表示若只考虑前 \(i\) 张牌，能获得的最大收益。

转移枚举第 \(i\) 张牌是否是在最后一次操作中被删，以及被哪个区间删。即 \(f_{i - 1}\) 和 \(\max_{j=1}^{i - 1}\{f_{j - 1} + \sum_{k=j}^iv_k \mid c_i = c_j\}\) 的较大值。

直接做是 \(n^3\) 的。区间求和那个部分可以前缀和优化，但仍然是 \(n^2\) 的，即 \(\max_{j=1}^{i - 1}\{f_{j - 1} + \sum_{k=1}^iv_k - \sum_{k=1}^{j-1}v_k \mid c_i = c_j\}\)。

可以把与 \(j\) 无关的提到外面，即 \(\sum_{k=1}^iv_k + \max_{j=1}^{i - 1}\{f_{j - 1} - \sum_{k=1}^{j-1}v_k \mid c_i = c_j\}\)。

然后这个就很好维护了。我们用桶维护每个 \(c_i\) 所对应的最大的 \(f_{i-1} - \sum_{k=1}^{i-1}v_k\)，转移可以优化成 \(\Theta(1)\)。总时间复杂度 \(\Theta(n)\)。

(2) P4342 [IOI1998] Polygon

• 有一个 \(n\) 个顶点 \(n\) 条边的环，顶点上有数字，边上有 \(+, \times\) 两种运算符号。

  首先删掉一条边，然后每次选择一条连接 \(V_1, V_2\) 的边，用边上的运算符计算 \(V_1\) 和 \(V_2\) 得到的结果来替换这两个顶点。

  求最后元素的最大值。

• \(n \le 50\)。

显然区间 DP。首先倍长破环为链。

设状态 \(f_{l, r}\) 表示将区间 \(l \sim r\) 内的数字处理后得到的最大数字。转移枚举断点 \(k\)，即 \(f_{l, r} = \max_{k=l}^{r-1} \operatorname{opt}(f_{l, k}, f_{k + 1, r})\)，其中 \(\operatorname{opt}\) 表示边上的运算符号。

这样做是不正确的。注意到两个负数相乘结果为正数，所以再维护 \(g_{l, r}\) 表示最小值。转移类似。

复杂度 \(\Theta(n^3)\)。

(3) P4933 大师

• 给定一个长度为 \(n\) 的序列。求有多少个子序列是等差数列。
• 设 \(v\) 为序列最大值。\(n \le 1000\)，\(v \le 20000\)。

设状态 \(f_{i, j}\) 表示有多少个以 \(i\) 结尾的子序列是公差为 \(j\) 的等差数列，且长度大于 \(1\)。

转移枚举倒数第二个元素 \(k\)，即 \(f_{i, j} = \sum_{k=1}^{i - 1} \{f_{k, j} + 1\mid a_i - a_k = j\}\)。其中 \(+1\) 的原因是我们可以选择长度为 \(1\) 的子序列。

复杂度是 \(\Theta(n^2v)\) 的。考虑优化。

可以发现如果确定了 \(a_i, j\) 那么 \(a_k\) 的值是可以确定的，即 \(a_k = a_i - j\)。所以处理方法与 (1) 类似，维护桶表示每一个 \(a_i\) 对应的 \(f_{i, j} + 1\) 之和。注意这里还有一个未处理的 \(j\)，解决方法是将转移顺序改为先枚举 \(j\) 再枚举 \(i\)。这样在当前 \(j\) 这轮循环时就不需要考虑 \(j\) 的影响了。

时间复杂度 \(\Theta(nv)\)。