[BCSP-X 2024 12 月小学高年级组] 打怪升级

Luogu

IDLGB4159

Time1000ms

Memory512MB

DifficultyP3

动态规划 DP2024北京BCSP-X

Alice 在玩一个游戏，游戏共有 $n$ 个关卡，你需要操作 $1$ 个主角过关，主角有 $2$ 个属性： 1. 血量 2. 等级每关的 Boss 会对主角造成伤害（血量减小），第 $i$ 关的 Boss 对等级为 $j$ 的主角造成的伤害值为 $b[i][j]$。每关打完 Boss 后，在进入下一关前会得到一本经验书，你有 $2$ 个选择： 1. 回血：第 $i$ 关的经验书可以使血量增加 $a[i]$。 2. 改变等级：若假设主角当前等级为 now，使用经验书可以将等级变为 $[1, now + 1]$ 中的任意值。你需要在 $2$ 个选择中择一执行。已知主角的初始血量为 $m$，初始等级为 $1$，游戏过程中任意时刻血量必须 $>0$。现在请问，在通过第 $k$ 个关卡之后（可以使用第 $k$ 关的经验书），主角能达到的最大等级是多少？如果无法通过第 $k$ 关，答案为 0。请你输出 $k = 1 \sim n$ 的所有答案，注意这 $n$ 个询问是独立的。例如 $n = 3, m = 2, a = [2, 1, 1]$ $$b[1][1] = 1$$ $$b[2][1] = 2, b[2][2] = 3$$ $$b[3][1] = 3, b[3][2] = 3, b[3][3] = 3$$ - 当 $k = 1$ 时，第一关血量先减为 $2 - 1 = 1$，然后选择升为 2 级，答案为 $2$。 - 当 $k = 2$ 时，第一关血量先减为 $2 - 1 = 1$，然后选择加血 $1 + 2 = 3$；第二关血量减为 $3 - 2 = 1$，然后选择升为 $2$ 级，答案为 $2$。 - 当 $k = 3$ 时，无论如何选择都无法通过第 3 关，答案为 $0$。 ## Input 第一行 $2$ 个整数 $n, m$，代表关卡数量和初始血量。第二行 $n$ 个整数 $a[1 \sim n]$ 代表每关经验书的加血量。接下来 $n$ 行，第 $i$ 行包含 $i$ 个整数代表第 $i$ 关的 Boss 对等级为 $1 \sim i$ 的主角造成的伤害值。 ## Output 输出 $n$ 行，第 $i$ 行包含 $1$ 个整数代表通过第 $i$ 个关卡之后，主角能达到的最大等级。 [samples] ## Note ### 样例 3-5 见附件。 ### 数据范围对于所有数据，$1 \leq n \leq 1500, 0 \leq a[i], b[i][j] \leq 100, 1 \leq m \leq 1500$ 本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。 | 子任务编号 | 分值 | $n$ | 子任务依赖 | |:----------:|:----:|:-------:|:------------:| | 1 | 39 | $\leq 10$ | | | 2 | 43 | $\leq 100$ | 1 | | 3 | 18 | $\leq 1500$ | 1,2 |

Samples

Input #1

Output #1

2
2
0

Input #2

10 98
67 100 76 15 44 86 38 95 5 8
43
25 91
14 18 24
79 79 60 85
35 47 59 22 96
53 78 43 95 55 25
74 26 97 30 42 14 6
100 70 79 49 83 74 43 38
64 38 75 79 59 10 54 17 2
34 19 19 4 23 90 99 97 93 10

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[BCSP-X 2024 12 月小学高年级组] 打怪升级",
    "description": {
      "content": "Alice 在玩一个游戏，游戏共有 $n$ 个关卡，你需要操作 $1$ 个主角过关，主角有 $2$ 个属性： 1. 血量 2. 等级 每关的 Boss 会对主角造成伤害（血量减小），第 $i$ 关的 Boss 对等级为 $j$ 的主角造成的伤害值为 $b[i][j]$。 每关打完 Boss 后，在进入下一关前会得到一本经验书，你有 $2$ 个选择： 1. 回血：第 $i$ 关的经验书可以使",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4159"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice 在玩一个游戏，游戏共有 $n$ 个关卡，你需要操作 $1$ 个主角过关，主角有 $2$ 个属性：\n\n1. 血量\n2. 等级\n\n每关的 Boss 会对主角造成伤害（血量减小），第 $i$ 关的 Boss 对等级为 $j$ 的主角造成的伤害值为 $b[i][j]$。\n\n每关打完 Boss 后，在进入下一关前会得到一本经验书，你有 $2$ 个选择：\n\n1. 回血：第 $i$ 关的经验书可以使...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments