DP1

P2523 [HAOI2011] Problem c

从后往前考虑，容易判掉无解。

启发我们计数也从后往前考虑，设 \(f[i][j]\) 表示考虑到 \([i, n]\) 的位置，确定了 \(j\) 个人的编号的方案数。

转移枚举之前确定了多少个人、在当前位置确定多少个人即可。

CF311B Cats Transport

求出正好接到每只小猫的出发时间 \(a_i\)，将小猫 \(a\) 升序排序，记 \(s_i\) 为 \(a\) 的前缀和，朴素的 dp 转移：设 \(f_{i, j}\) 表示考虑前 \(i\) 个铲屎官接走前 \(j\) 只小猫的最小代价。则 \(f_{i, j} = \min(f_{i, j}, f_{i - 1, k} + a_j \times (j - k) - (s_j - s_k))\)。

划分成 \(p\) 段的最小代价 —— 想到 WQS 二分相关的优化技巧。

不过这题没必要 WQS 二分，简单地套个斜率优化就可以了。

斜率优化推式子部分：

\(f_{i - 1, k} + s_k = a_{j}k + f_{i, j} + s_{j} - ja_{j}\)。

令 \(y = f_{i - 1, k} + s_{k}, slope = a_j, x = k, b = f_{i, j} + s_{j} - ja_j\)。

斜率单增，求 \(b\) 的最小值，维护一个下凸包即可。时间复杂度 \(O(pm)\)。

P4056 [JSOI2009] 火星藏宝图

可以把直接跳分解成先向下走再向右走，则从同一列的若干点直接转移到后面的点 \(x\)，一定选取这一列能转移到 \(x\) 的最下方的点进行转移（从收益和代价分别考虑）。这个可以 \(O(m^2)\) 预处理。

将所有点按列为第一关键字，行为第二关键字排序，枚举每个点以及从哪一列转移过来，可以得到 \(O(nm)\) 的做法。

推式子，发现是可以斜率优化的形式。稍微分析一下可以发现之前的枚举顺序不好优化，因为每列的最大行时刻都在变化。

换一下顺序，按行为第一关键字，列为第二关键字进行更新，记 \(f_{i, j}\) 表示到第 \(i\) 行第 \(j\)​ 列的最大权值。

\(f_{i, j} = \min(f_{i, j}, f_{pos_{x}, x} - (i - pos_x)^2 - (j - x)^2 + w_{i, j})\)。其中 \(pos_x\) 表示第 \(x\) 列能转移当前点的最大行，这个可以 \(O(1)\) 实时更新，且支持每一行开一个单调队列进行斜率优化。

斜率优化推式子部分：

\(f_{pos_x, x} - (i - pos_x)^2 - x^2 = -2jx + f_{i, j} + j^2 - w_{i, j}\)。

令 \(y = f_{pos_x, x} - (i - pos_x)^2 - x^2, slope = -2j, x = x, b = f_{i, j} + j^2 - w_{i, j}\)。

斜率单减，求 \(b\) 的最大值，维护一个上凸包即可。时间复杂度 \(O(m^2)\)。

由于当前点可以由该列上方转移过来，因此实现时要先把当前位置插进队列再进行后续操作。

P2569 [SCOI2010] 股票交易

因为 \(AP_i \ge BP_i\)，所以一天内要么买要么卖。

设 \(f_{i, j}\) 表示第 \(i\) 天持有 \(j\) 支股票的最大收益。

• 啥也不做：\(f_{i, j} = f_{i - 1, j}\)。

• 第一次买：\(f_{i, j} = -j\times AP_i\)。

• 隔 \(K\) 天买：\(f_{i, j} = \max(f_{i - K - 1, k} - (j - k)\times AP_i) (j - k \le AS_i)\)。

• 隔 \(K\) 天卖：\(f_{i, j} = \max(f_{i - K - 1, k} + (k - j) \times BP_i)(k - j \le BS_i)\)。

能直接用 \(f_{i - K - 1}\) 更新 \(f_i\) 的原因是因为 \(f_{x}\) 相较于 \(f_{x - 1}\) 一定不劣（因为可以啥也不做）

直接枚举 \(i, j, k\) 是 \(O(n^3)\) 的，但可以从小到大枚举 \(j\)，滑动窗口维护 \(j - k \le AP_i\) 的 \(f_{i - K - 1, k} + k \times AP_i\) 的最大值，对于卖的情况类似处理，从大到小枚举即可。

P2317 [HNOI2005] 星际贸易

做一遍背包，求出最大贸易额。题目保证了只有一种获得最大贸易额的方法，因此可以通过倒推 dp 数组确定必经星球。

然后求第二问。燃料数的有效范围是 \(2n\)，因此可以把 \(R\) 砍下来。

设 \(f_{i, x}\) 表示在第 \(i\) 个星球停靠并进行加燃料和维护后，飞船上燃料数为 \(x\) 的最小花费。

\(f_{i, x} = \min(f_{j, y} + (x - y + 2)\times P_i + F_i), L_{i} - L_j \le L_0, 2\le y \le x + 2\)。

滚动优化：\(f_{i, x} = \min(f_{i, x - 1} + P_i, f_{j, x + 2} + F_i)\)，省去了枚举之前油量的步骤。

对每一个 \(x\) 开一个单调队列，维护 \(L_i - L_j \le L_0\) 时 \(f_{j, x + 2}\) 的最大值。

注意当枚举到必经星球时，需要把队列清空，只保留当前星球。

P2515 [HAOI2010] 软件安装

将 \(i\) 向 \(D_i\) 连边，每个连通块都是一棵基环树，直接用 tarjan 缩一遍点就转成了森林，且其中的每一棵有向树都是根向树。

选一些点获得权值，同时消耗容量，如果一个点被选，则它的父亲也要被选。

做树上背包即可。

由于一些奇怪的原因树上背包挂了一个晚上，并且现在还不知道怎么回事。

P4190 [CTSC2010] 三国围棋擂台赛

状压，记忆化搜索。记 \(f[S0][S1][S2][a][b][x]\) 表示三国分别还剩哪些人、\(a\) 作为上一场胜方与 \(b\) 比赛、\(x\) 为上一场胜者的概率。