算法 1 期末测试

最长倍增子序列

• 分析：
• 解法一：动态规划
• 与最长上升子序列的写法基本相同，状态转移的判断从 a[i] > a[j] 改为 a[i] >= a[j] * 2 即可。
• 时间复杂度 $O(n^2)$ 。
• 解法二：贪心
• 与最长上升子序列的贪心解法原理相同，时间复杂度 $O(n\log n)$ 。

• 参考代码：

传纸条 II

• 30 分解法：类似迷宫问题统计路径方案数的写法，dfs 过程中控制路径不要穿过对角线即可。

• 80 分解法：
• 动态规划，dp\[i][j] 表示从起点走到 (i, j) 不穿过对角线的方案数。
• 只走 j <= i 的位置 (i, j) 即可，这样就不会穿过对角线。
• 对于 j >= i 的情况，与 j <= i 是对称的，方案数相同，最后结果是 dp\[n][n] * 2。

• 分析（满分解法）：
• 要往右和往下各走 n - 1 步，不穿过对角线问题，是卡特兰数列对应的经典问题，结果是卡特兰数列第 n - 1 项的值 $H(n-1)$ 。
• 同样的，i <= j 和 j <= i 这两个条件是对称的，最终结果是 $2\cdot H(n-1)$ 。

• 参考代码：

混动燃料

• 30 分解法：dfs 对于每桶燃料选或不选进行 01 枚举，搜索所有方案，取最大的热值。

• 另外 50 分解法：将单位统一为升，转换为普通的 01 背包。

• 分析（满分解法）：
• 将单位统一为毫升，发现容量大，但总热值较小，转换为“容量大价值小”的 01 背包问题，对应作业题的“巨型背包”。
• dp\[i][j]：前 i 桶燃料中，选出总热值恰好为 j 的燃料最小体积。
• 状态转移和边界参考“巨型背包”。
• 需要滚动数组优化空间。

• 参考代码：

小图的预算方案

• 分析：
• 类似分组背包。
• dp\[i][j]：在前 i 家商店中，消费不超过 j 元的最大快乐值。
• 状态转移：
• 不在第 i 家商店消费，dp\[i-1][j]
• 在第 i 家商店消费 k 元，dp\[i-1][j-k] + a\[i][k]
• 在所有选择中决策取 max 为 dp\[i][j] 的值
• 边界：dp\[0][0~m] = 0
• 时间复杂度：$O(nm^2)$

• 参考代码：

移球计数

• 40 分解法：dfs 暴力搜索每种方案。

• 分析（满分解法）：
• dp\[i][j]：经过 i 次移动，到达位置 j 的方案数。
• 因为可以往负方向移动，所以位置 j 有可能是负数，a[i] 最大是 100，最多 1000 次移动，所以极端情况 j = -100000，负数不能作为数组下标。
• 将题意进行以下转换：起点从位置 0 改为 $10^5$，目标从位置 m 改为 m + $10^5$，这样位置的范围从 $-10^5\sim 10^5$ 转换为 $0\sim 2\times 10^5$ ，就不会出现负数位置。
• 状态转移：对于 dp\[i][j]，考虑第 i 次移动的选择
• 保持不动：dp\[i-1][j]
• 之前在 j - a[i] 位置，往正方形移动到 j：dp\[i-1][j-a[i]]
• 之前在 j + a[i] 位置，往负方向移动到 j：dp\[i-1][j+a[i]]
• 根据加法原理，将以上三类情况对应的方案数加起来就是 dp\[i][j] 的值。
• 边界：0 次移动，位于起点的方案数为 1，dp\[0][100000] = 1
• 根据数据范围，需要滚动数组优化空间。

• 参考代码：

最优划分

• 分析（40 分解法）：
• dp[i]：前 i 个数字最多划分的段数
• 状态转移：
• dp[i] 赋一个负无穷的初始值，表示无法分段。
• 枚举 j，表示前 j 个数字分段，第 j + 1 ~ i 个数字作为最后一段。
• 前提 1：第 j + 1 ~ i 个数字要有 k 个 0 或 k 个 1。（可预处理前缀和，此处快速计算这段区间 0 和 1 的个数）
• 前提 2：前 j 个数字要能够分段。
• 前 j 个数字最多分成 dp[j] 段，加上最后这一段，共有 dp[j] + 1 段，取最大的 dp[j] + 1 就是 dp[i] 的值。
• 边界：
• 0 个数字分为 0 段，dp[0] = 0。
• 时间复杂度：两层循环，$O(n^2)$ 。

• 分析（满分解法）：
• 注意到对于满足有 k 个 0 的一段数字 [j + 1, i]，当右端点 i 继续往右移动到 i'，且 s[i'] == '0'，显然此时有 k + 1 个 0，为了保持 k 个 0，左端点 j + 1 也要往右移动。保持 k 个 1 也同理。根据这个发现可设计如下 dp 优化上面 40 分解法中第二层循环 j 的枚举。
• dp\[i][0]：前 i 个数字中，最后一段满足有 k 个 0 的最多划分段数。
dp\[i][1]：前 i 个数字中，最后一段满足有 k 个 1 的最多划分段数。
• 状态转移（以 dp\[i][0] 为例）：
• 如果 s[i] == '0'，记 p[0] 是满足 p[0] ~ i - 1 这一段有 k 个 0 的最大左端点，那么 p[0] + 1 ~ i 这一段有 k 个 0，还有 p[0] + 2 ~ i、p[0] + 3 ~ i ......，不断令左端点 p[0] + 1 往右移动，直到 0 的个数变为 k - 1。
前 p[0] 个数字分段的最大段数是 max(dp\[p[0]]\[0], dp\[p[0]]\[1]) ，加上最后一段，所以取最大的 max(dp\[p[0]]\[0], dp\[p[0]]\[1]) + 1 就是 dp\[i][0] 的值。
• 如果 s[i] == '1'，只要前 i - 1 个数字划分的最后一段有 k 个 0，再把 s[i] 加入最后一段，仍然满足有 k 个 0，所以 dp\[i][0] = dp\[i-1][0] 。
• 时间复杂度：p[0] 和 p[1] 只会往右移动，总复杂度 O(n)。

• 参考代码：