Problem : Maximum Contest Score / 竞赛总分

​版权信息​：USACO

---

任务总览

任务名称	时间限制	内存限制	分数
竞赛总分	1 sec	1024 MB	5 points

---

题目描述

USACO 竞赛的目标是让学生尽可能多地得分。因此，在设计竞赛时，我们希望选取适当的题目，使得选手能在 固定的总时间 M 内获得尽可能高的总分。

​竞赛规则如下​：

• 竞赛总时间为 M 分钟（1 ≤ M ≤ 10000）。
• 题目共有 N 种类型（1 ≤ N ≤ 10000）。
• 每种类型的题目可以 ​无限制地选择​。
• 每种题型有：
  • points（解答此题所得的分数，1 ≤ points ≤ 10000）。
  • minutes（解答此题所需的时间，1 ≤ minutes ≤ 10000）。

​目标​：选择若干道题目，使得 ​总时间不超过 M​，并且 ​总得分最高​。

---

输入格式

• 第一行 包含两个整数 M 和 N，用空格隔开：
  • M（竞赛的总时间）。
  • N（题目类型的数量）。
• ​接下来的 N 行​：
  • 每行包含 两个整数points 和 minutes：
    • points（该题目的 ​分数​）。
    • minutes（该题目的 ​耗时​）。

---

输出格式

• 输出一个整数，表示在 ​**M 分钟内能获得的最大总分**​。

---

输入输出示例

输入示例 1

300 4
100 60
250 120
120 100
35 20

输出示例 1

605

解释

• 选取 ​第 2 种题目 2 次​（250×2 = 500 分）。
• 选取 ​第 4 种题目 3 次​（35×3 = 105 分）。
• 总得分 ​605 分​，总耗时 120×2 + 20×3 = 300 分钟，刚好等于 M。

---

题目分析与解法

这是一个 ​完全背包问题​，其中：

• 背包容量 为 M（竞赛总时间）。
• 物品 为 N 种题型，每种题型可以 ​选取无限多次​。
• 价值 为 points（题目分数）。
• 重量 为 minutes（题目所需时间）。
• ​目标​：在 M 分钟内 ​最大化总分数​。

动态规划解法

定义 dp[j] 表示 ​总时间不超过 j 时的最大分数​，状态转移方程：

$dp[j] = \max(dp[j], dp[j - minutes[i]] + points[i])$其中：

• dp[j] 代表 ​总时间 j 时的最大得分​。
• 遍历所有题型 i，若选择该题，则 ​**当前时间 j 需要减去 minutes[i]**​，并加上它的分数 points[i]。

优化策略

1. ​**采用顺序遍历 j**​（因为完全背包问题允许重复选择）。
2. ​时间复杂度​：
   • 题目种类 N ≤ 10000，竞赛时间 M ≤ 10000，时间复杂度 ​**O(N × M)**​，最多约 10^8 次计算，在 1 秒内可接受。

---

时间复杂度分析

步骤	复杂度
读取输入	O(N)
计算最大得分	O(N × M)
总复杂度

由于 N ≤ 10000 且 M ≤ 10000，即 10^8 次计算，动态规划方法是可行的。