题解

问题分析

题目要求从 $n$ 道题中每道题选择至少一个子任务，使得总得分恰好为 $s$。每道题有多个子任务，分值不同，需要找到一种选择方案。

关键约束

1. 每道题必须至少选一个子任务（不能得零分）
2. 总得分恰好等于 $s$
3. 子任务总数有限制：$\sum k_i \leq 100,000$
4. 总状态数限制：$(\sum k_i) \cdot s \leq 10^7$

算法思路

动态规划 + 状态压缩：

状态定义

• dp[i][x] 表示处理完前 $i$ 道题，总得分为 $x$ 时，最后一道题选择的子任务编号
• 值为 $-1$ 表示该状态不可达

状态转移

对于第 $i$ 道题的每个子任务 $j$ 分值 $c$：

对于 x 从 s-c 到 0 逆序：
    如果 dp[i][x] 或 dp[i+1][x] 可达，且 dp[i+1][x+c] 未被设置：
        设置 dp[i+1][x+c] = j

关键技巧

1. 逆序枚举：避免同一子任务被重复选择
2. 状态继承：dp[i+1][x] 可以从 dp[i][x] 继承，表示第 $i+1$ 题还没选子任务
3. 回溯构造：从最终状态 dp[n][s] 反向追踪每道题选择的子任务

复杂度分析

• 时间复杂度：$O((\sum k_i) \cdot s)$，在约束 $(\sum k_i) \cdot s \leq 10^7$ 内可接受
• 空间复杂度：$O(n \cdot s)$，使用滚动数组可优化但代码中未使用

算法步骤

1. 初始化：dp[0][0] = 0，其他为 $-1$
2. 动态规划：
   • 遍历每道题
   • 遍历该题每个子任务
   • 逆序更新 DP 状态
3. 检查可行性：dp[n][s] != -1
4. 回溯构造答案：
   • 从 (n, s) 状态开始
   • 根据 dp[i][x] 记录的子任务编号回溯
   • 确保每道题至少选一个子任务
5. 输出方案

样例分析

样例1：无法凑出总分 4

• 第一题：只有子任务 [2]，必须选得 2 分
• 第二题：子任务 [3, 1]，组合无法得到总分 4
• 输出 No

样例2：可以凑出总分 4

• 第一题：选子任务 1 得 2 分
• 第二题：选子任务 1 得 2 分
• 总分 2+2=4，输出 Yes

算法标签

• 动态规划
• 状态压缩
• 背包问题
• 回溯构造
• 可行性判断