DP 复习

HDU-1159 Common Subsequence

最长公共子序列板子题。

dp[i][j] = \begin{cases} dp[i - 1][j - 1] + 1 & (s_{i} = t_{j}) \\ \max(dp[i - 1][j], dp[i][j - 1]) \\ otherwise \end{cases}

由于是连续值，可以先预处理出数组 $a, b$ 的满足条件的最长公共子序列。

\begin{aligned} fa[a[i]] &= fa[a[i] - 1] + 1 \\ fb[b[i]] &= fb[b[i] - 1] + 1 \end{aligned}

然后枚举最后的答案以哪个数字结尾就可以了，即：

ans = max\{fa[i] + fb[i]\}

由于没有个数的限制，所以对于每个物品 $(x, y, z)$ 可以拆成 $(x, y, z), (x, z, y),(y, z, x)$ ，所以剩下的问题就可以用 DP 解决了。

定义 $dp_{i}$ 表示将 $i$ 放在最上面的塔的最高高度。

dp[i] = max_{1 \le j < i}(dp[i], dp[j] + a[i].z)

最长不上升子序列板子题。

dp_{i} = \max_{a_{j} \le a_{i}}(dp_{i}, dp_{j} + 1)

首先记 $dp_{i}$ 表示只使用魔法在时刻 $i$ 的最远移动距离，则有：

\begin{aligned} &dp_{i} = \max \begin{cases} dp_{i - 1} + 60 & m \geq 10 \\ \\ dp_{i-1} & otherwise \end{cases} \\ \\ &m \leftarrow m + 4 \end{aligned}

然后对 $dp_{i}$ 进行微调：

dp_{i} = \max(dp_{i}, dp_{i-1} + 17)

判断是否存在 $dp_{i} \geq S$ 即可。

由于从前往后处理的约束条件很多，不妨从后往前处理。

令 $dp_{i}$ 表示在 $i$ 时刻的最大空闲时间，则有：

dp_{i} = \max_{j, l_{j} = i}(dp_{i}, dp_{i + r_{j}});

如果不存在 $j$ 使得 $l_{j} =i$ ，则：

dp_{i} = dp_{i + 1} + 1

先对区间进行排序，定义 $dp_{i}$ 表示前 $i$ 个区间里能吃到的最多的草堆的个数。

\begin{aligned} dp_{i} = \max_{\forall j, r_{j < i}} (dp_{i-1}, dp_{j} + (r_{i} - l_{i} + 1)) \end{aligned}

由于这样的转移是 $O(n^2)$ 的，我们需要优化。

考虑排序后区间具有单调性，需要的条件又为 $r_j < i$ ，则可以对满足条件的 $j$ 进行二分，复杂度为 $O(n \log n)$ 。

定义 $dp_{i,j,k,l}$ 表示 $4$ 种类型的卡片分别有 $i,j,k,l$ 张时的最大得分。

dp_{i,j,k,l} = \max \begin{cases} dp_{i - 1,j,k,l} + a_{i + 2 \times j + 3 \times k + 4 \times l} & i > 0 \\ dp_{i,j - 1,k,l} + a_{i + 2 \times j + 3 \times k + 4 \times l} & j > 0 \\ dp_{i,j,k - 1,l} + a_{i + 2 \times j + 3 \times k + 4 \times l} & k > 0 \\ dp_{i,j,k,l - 1} + a_{i + 2 \times j + 3 \times k + 4 \times l} & l > 0 \\ \end{cases}

区间 DP，定义 $dp_{i, j}$ 表示区间 $[i, j]$ 满足条件的最小操祚次数。

转移如下：

如果 $a_{i} = a_{j}$ ，则 $dp_{i, j} = dp_{i + 1, j - 1}$ ;
$\forall i, j$ ， $dp_{i, j} = \min(dp_{i, j}, dp_{i + 1, j} + 1, dp_{i, j - 1} + 1, dp_{i + 1, j - 1} + 1)$ 。

定义 $dp_{i, j}$ 表示当枚举到 $a$ 的第 $i$ 位和 $b$ 的第 $j$ 位时的答案。

dp_{i, j} = \begin{cases} dp_{i - 1, j} + dp_{i, j - 1} + 1 & a_{i} = b_{j} \\ dp_{i - 1, j} + dp_{i, j - 1} - dp_{i - 1, j -1} & otherwise \end{cases}

定义 $f_{i}$ 表示长度为 $i$ 的前缀是否可以北分解为集合 $P$ 中的元素。

枚举以 $s_{i}$ 结尾的后缀，看是不是集合 $P$ 的元素，设枚举的后缀长度为 $j$ , 则：

dp_{i} = dp_{i} \operatorname{||} dp_{j}

由于题面中说明了 $P$ 中的元素长度不会超过 $10$ , 所以复杂度为 $O(10n) = O(n)$ ，~~常数较大但可过~~。

这题有一个很有趣的性质：

每一行的限制时相互独立的

所以对于每一行，我们定义 $f_{i, j}$ 表示处理到第 $i$ 行的第 $j$ 列时的最大收益。则有：

f_{i, j} = \max(f_{i, j - 1}, f_{i, j - 2} + a_{i, j})

令 $\displaystyle g_{i} = \max_{1\leq j\leq m}(f_{i, j})$ ， $t_{i}$ 为处理到第 $i$ 行时的最大收益，同上可得：

t_{i} = \max(t_{i - 1}, t_{i - 2} + g_{i})