NOIP2024集训Day20 DP常见模型1 - 序列

NOIP2024集训Day20 DP常见模型1 - 序列

A. [JOI2022 Final] Let's Win the Election

贪心+DP。

首先，一定是所有协作者同时在同一个州演讲，这样才最优。

然后，假设我们已经知道所有州的方案（支持、支持+协作、反对），那我们一定是先按照从小到大的顺序拿下所有“支持+协作”州，这样最优。

然后我们先考虑枚举“支持+协作”州的数量，然后 dp。

设 \(f_{i, j, k}\) 表示考虑到第 \(i\) 个州，有 \(j\) 个支持州，有 \(k\) 个“支持+协作”州，即 \(k\) 个协作者的最优时间方案。dp 的时间复杂度为 \(O(n^3)\)，再加上枚举“支持+协作”州的数量，总时间复杂度 \(O(n^4)\)。考虑优化。

经过一番探索，我们可以发现：当两个“支持+协作”州之间有反对州时，将反对州与后面一个“支持+协作”州位置交换一定会更优。进一步得到：两个“支持+协作”州之间一定没有反对州。那我们就可以去枚举最后一个“支持+协作”州的位置 \(i\)，这样就省去了之前 \(k\) 那一维，最后一个“支持+协作州”后面的答案就是 \([i + 1, n]\) 中选择 \(k - i\) 个 \(a_i\) 的最小和，这部分可以使用背包预处理。dp 的复杂度也降到了 \(O(n^2)\)，总的时间复杂度为 \(O(n^3)\)。可以通过。

B. [JOISC2015 Day1] 有趣的家庭菜园 2

\(i\) 能收获的条件为它是其中一侧的最大值。

设 \(f_i\) 表示 \(1...i\) 中必选 \(i\) 的答案，\(g_i\) 表示 \(i...n\) 中必选 \(i\) 的答案

那么答案就是 \(\max\limits_{i = 1}^n f_i+g_i-p_i\)。

\(f\) 和 \(g\) 一个顺着，一个倒着，不妨讨论 \(f\)，\(g\) 同理即可。

显然 \(f_i = \max(f_j - \sum\limits_{k = j + 1}^{i - 1} c_k\cdot[h_k\gt h_i])(0\le j \lt i)\)。

但这显然过不了，因为 \(\Theta(n^3)\)。进行优化。

可以发现从左一次往右时 \(h_i\) 会影响比他矮的节点，\(f_j - \sum\limits_{k = j + 1}^{i - 1} c_k \cdot [h_k \gt h_i]\) 就是开区间 \((i, j)\) 中比 \(j\) 高的所有草的费用之和，即遇到一个 \(h_i\) 时就算它的影响。

可以用线段树维护，对 \(h\) 离散化，再对高度建一棵线段树。

对于当前点 \(i\)，先找线段树 \([1, h_i]\) 中权值最大的点更新 \(f_i\)（这里的 \(h_i\) 指离散化后的编号数组，后面也是）

然后让线段树中 \([1, h_i)\) 的值减去 \(c_i\)，最后把 \(f_i\) 插入线段树中 \(h_i\) 的位置。

D. [LOJ 6191] [美团 CodeM 复赛] 配对游戏

概率期望dp。

显然任何时刻栈中的元素自底至顶一定是若干个 \(0\) 加若干个 \(1\)。

但是如果设状态 \(p_{i, j, k}\) 表示前 \(i\) 次操作，栈中 \(j\) 个 \(0\)，\(k\) 个 \(1\) 的概率，复杂度是 \(\Theta(n^3)\) 的，显然会TLE。

注意到 \(0\) 的个数对状态转移是没有影响的，而期望在任何时刻都具有可加性，因此可以设 \(f_{i, j}\) 表示前 \(i\) 次操作，栈中 \(j\) 个 \(1\) 的期望元素个数。

那么直接考虑新加入一个是 \(0\) 还是 \(1\)，看一下长度是增加还是减少即可。

这里有一个问题：每次增加或减少的长度是多少？由于我们设的是总情况的期望，而期望等于概率*权值，这种情况的权值为 \(1\)，因此期望值就是这种情况的概率。

所以还需要维护一个 \(p[i][j]\) 表示前 \(i\) 次操作，栈中 \(j\) 个 \(1\) 的概率。每次使用概率转移期望即可。

时间复杂度 \(\Theta(n^2)\)。

E. CF1515E Phoenix and Computers

新学一种连通块DP。

连通块DP与区间DP略有类似，但是维护方式大相径庭。

对于连通块DP：

这种DP主要维护一个一个的块，通常有三种操作，状态定义为：设 \(f_{i, j}\) 为放置 \(i\) 个元素，形成了 \(j\) 个块的方案数。

1. 操作一：将某个块的元素个数加一

   因为每一个块都有可能加一，所以：\(f_{i,j} = f_{i - 1, j} \times j\)。

2. 操作二：新增一个块

   类似插空的思路。原来有 \(j - 1\) 个块，所以有 \(j\) 个空。

   故：\(f_{i,j} = f_{i - 1, j - 1} \times j\)。

3. 操作三：合并两个块

   与第二点类似，但不能在两边插空。所以还是有 \(j\) 个空。

   故：\(f_{i, j} = f_{i - 1, j + 1} \times j\)。

时间复杂度 \(\Theta(n^2)\)。以上为基本操作。

对于这道题：

从小到大给元素排序。还是这三种操作，同样的状态定义。

1. 新增元素

   对于一个新增加的元素，有两种情况。

   直接加入：\(f_{i,j} = f_{i - 1, j} \times j \times 2\)

   隔一个加入，这样就会有一个自动生成，相当于加了两个：\(f_{i, j} = f_{i - 2, j} \times j \times 2\)

2. 新增块

   直接加就好了：\(f_{i, j} = f_{i - 1, j - 1} \times j\)

3. 合并块

   也有两种情况。

   两个块之间空了两个格子，随便加一个：\(f_{i, j} = f_{i - 1, j + 1} \times 2 \times j\)

   两个块之间空了三个格子，加中间一个：\(f_{i, j} = f_{i - 3, j + 1} \times j\)

这样就做完了。

F. [PA2021] Od deski do deski

计数类DP。

难点在于状态的定义吧。自己一开始是设 \(f_{i, j}\) 表示序列中有 \(i\) 个元素，最后一个元素为 \(j\) 的合法方案数，但是这样很不好转移，因为我们不知道 \(j\) 是否可以和之前的某一个数匹配。所以我们改变 \(f_{i, j}\) 表示序列中一共有 \(i\) 个数，在当前情况的序列后面加 \(j\) 种数能使序列变为合法序列的方案数。但问题是，我们不知道当前状态是否合法。所以再加一维 \(0/1\) 表示是否合法。

然后就来到状态转移了。首先需要知道两个性质：

• 如果在序列后面加 \(j\) 种数使得序列变得合法，那么加另外 \(m - j\) 种数就一定不合法。
• 如果序列 \(A\) 合法，那么形如 \(A + x + B + x\) 的序列是一定合法的，形如 \(A + x + B\) 的序列是一定不合法的，其中 \(B\) 表示不包含 \(x\) 的任意序列。

转移方程如下：

\(\begin{cases}f_{i + 1, j, 1} = f_{i + 1, j, 1} + f_{i, j, 1} \times j \\ f_{i + 1, j + 1, 0} = f_{i + 1, j + 1, 0} + f_{i, j, 1} \times (m - j) \\ f_{i + 1, j, 0} = f_{i + 1, j, 0} + f_{i, j, 0} \times (m - j) \\ f_{i + 1, j, 1} = f_{i + 1, j, 1} + f_{i, j, 0} \times j \end{cases}\)