2192: 2026DP综合评测
Description
DP 综合复习与测评
1. 动态规划基础流程“青蛙跳台阶”（8 分，4 题 * 2 分）
[题意] 小明家门口有一排 n 级台阶（n ≤ 30）。 一只青蛙每次可以跳 1 步、2 步 或 3 步。 问
青蛙从地面跳到第 n 级台阶，共有多少种跳法？
以下是此题目的解题思路框架，用“√”“×”符号判断以下描述的对错：
（1）（ ）首先，我们需要设计合理的状态。需要一维动态规划数组 dp[35]，状态 dp[i]代表“每次停在第 i 级台阶上时跳跃的最少次数”。
（2）（ ）然后，我们需要设计怎么转移状态。青蛙每次可以跳 1 步、2 步或 3 步，所
以 dp[i] 通过 dp[i-1]，dp[i-2]，dp[i-3] 计算得出。
（3）（ ）此外，我们需要考虑初值和边界条件。（约定台阶从 1 开始）若我们在转移
过程中规定了“如果要用 dp[i-j] 的值需保证 i-j > 0”，则仅需要计算一个初值 dp[0] = 0。
（4）（ ）最后，我们考虑最终结果。我们的答案是 dp[n]。
2. 背包问题的循环运算顺序“红宝石和蓝宝石”（12 分，4 题 * 3 分）
[题意] 一个人去珠宝店买宝石，珠宝店有 n 串不同长短的混合宝石，每一串由若干颗不同数量的红宝石和蓝宝石串成，不能分拆出售。问如果想买不超过 m1 颗红宝石，m2 颗蓝宝石，那
么此人最多能买多少串？
显然这是一个背包问题，状态 dp[i][j][k] 代表看到第 i 串时，红宝石空间剩 j，蓝宝石空间剩
k 时的最多串数。
用“√”“×”符号判断以下描述的对错：
（1）（ ）这是个 0-1 背包问题。（2）（ ）最理想的（最优的）空间复杂度是 O(n*m1*m2)。
（3）（ ) 循环层级可以是（当前串序数）{（红宝石空间）{（蓝宝石空间）{（计算 dp）}}}。
（4）（ ）使用节省空间技巧后，对红宝石空间的循环顺序应当从小到大。
3. 环形状态上的区间 DP“能量项链”（12 分，3 题 * 4 分）
[题意] 在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。相邻的两颗珠子（前一颗
珠子的尾标记一定等于后一颗珠子的头标记）能聚合成一颗珠子，同时释放出可以被吸盘吸
收的能量。如果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾
标记为 n，则聚合后释放的能量为 m*r*n（Mars 单位），新产生的珠子的头标记为 m，尾
标记为 n。 需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链
上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合
顺序，使一串项链释放出的总能量最大。
例如：设 N=4，4 颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记
号⊕表示两颗珠子的聚合操作，(j⊕k)表示第 j，k 两颗珠子聚合后所释放的能量。则第 4、1
两颗珠子聚合后释放的能量为： (4⊕1)=10*2*3=60。 这一串项链可以得到最优值的一个聚
合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710
选择唯一正确的描述：
（1）（ ）通过复制链可以覆盖到所有的环形情况。最终的链长至少增加到？A. N + 1
B. 2N + 1
C. 2N - 1
（2）（ ）为了保证计算单个状态时可以利用已算出的结果，以下哪种分配循环的思路
更加合理？
A. 最外层按顺序枚举链上已考虑到第 i 个元素，其内侧的循环按区间长和区间分割点分配。
B. 最外层枚举选择的区间长度 l，其内侧的循环按区间起点和分割点分配。
C. 两个外层枚举选择合并的区间长度 l1和 l2，其内侧的循环按区间起点分配。
（3）（ ）N 最多为 100，推测最终算法的时间复杂度。
A. O(N2log(N))
B. O(N2)
C. O(N3)
4. 树形 DP 与记忆化搜索“周年庆宴会”（10 分，2 题 * 5 分）
[题意] 某大学有 N 个职员，举办周年庆宴会，编号 1 到 N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个人都有一个欢乐值，为了
让气氛更好，要求在这 N 个人中选一些人去参加宴会，并且选出的这些人中任意两个人之
间都没有直接上司或直接下属关系，求选出人的最大欢乐值。
这道题目需要在树上做巧妙的动态规划，需要考虑某个职员去或者不去。计算职员 u 时，
我们已经算出了该职员的所有下属（直系或非直系）的欢乐值情况。具体来说：
dp[0] 代表访问到 u 时，u 没有去时的所有 u 的下属的最大欢乐值；
dp[1] 则代表访问到 u 时且 u 去了时，自身与所有 u 的下属的最大欢乐值。
选择所有正确且有必要的描述：
（1）（ ）对 DP 状态的具体计算过程，正确的是哪些？A. 对于 dp[0]，直系下属可以去，通过把所有 u 的直接下属 v 的 max(dp[v][0]dp[v][1]) 加
起来计算。
B. 对于 dp[0]，直系下属可以去，通过把所有 u 的直接下属 v 的 dp[v][1] 加起来计算。
C. 对于 dp[1]，直系下属都不能去，通过把所有 u 的直接下属 v 的 dp[v][0] 加起来计算。
D. 对于 dp[1]，直系下属都不能去，通过把所有 u 的直接下属 v 的 dp[v][0] 及 u 自己的
欢乐值加起来计算。
（2）（ ）树形 DP 的思路和区间 DP 很像，都是把大范围问题拆成小范围问题求解。
我们在计算树形 DP 结果时运用了 DFS。以下保证用 DFS 计算树形 DP/其他 DP（记忆化搜索）的正确性的手段和描述中，正确且有必要的有哪些？
A. 在计算树形 DP 时，添加 visited 数组标记 u，保证点访问不重复。
B. 运用 dfs 递归计算（除树形外）DP 问题时，返回值须记录到 dp 数组中，仅数组内无记
录的情况下计算，否则直接用数组值，可以达到剪枝增加效率。
C. 在“周年庆宴会”中，由于每个 u 点需要计算 0 与 1 两种状态，dfs 可以没有返回值，
纯粹依赖 dp 数组记录值计算。
D. 记忆化搜索的时间复杂度和循环 DP 一致。
5. 状态压缩 DP 初探（8 分，2 题 * 4（2+2）分）
以下是一些状态压缩 DP 的常识描述，用“√”“×”符号判断以下描述的对错，然后简单写
一些原因：
（1）（ ) 通常题目数据范围在 20 以内时可以考虑状态压缩 DP；在 10 以内时可以有
两层枚举状态循环。
判断原因：
提示：和 2 的次方数量级相关
（2）（ ) 若 m 为状态空间总量，枚举压缩后状态可以从 1 到 1<<m 依次枚举。
判断原因（可不写）：
提示：每次状态之间的判别是否不被影响？
二、 编程实战（50 分）
选择了本学期讲解过但是没有同学完成补题的两道 NOIP/CSP 综合习题，这里给出思路提
示，大家可以尽量回忆讲解内容并尝试实现。（挑战自我的话不要看关键思路提示！）
1. 守望者的逃离（25 分）
关键思路提示：“你跑不过我你信不信.jpg”，无限时间情况下，用传送然后休息一定优于
纯跑，所以先考虑用 DP 算传送的解，再在 DP 结果上考虑加跑步优化；最后写出来的东西
可能不太像 DP，但是可以用 DP 的思路推一下然后优化空间成最后结果。
2. 上升点列（25 分）
关键思路提示：先按横纵坐标排序，然后“能多 k 个点”就像背包容量一样考虑成一个维度，
把两个欧式距离多于 1 的点连起来的代价就是两点间欧式距离-1。
Sample Input Copy
Sample Output Copy