← 返回题目列表

AtCoder · joi2023_yo2_d

D. 货运列车

中文机器翻译题面 查看原题

配点: 100 点

問題文

IOI 铁路是 1 经营一条铁路线。排列在IOI铁道线上 有 N 个站,按顺序 它们的编号最大为 1 从 N 。每个 i (1 \leqq i \leqq N - 1),车站 i 和车站 i + 1 由一条铁路线连接,其长度为 1 。

IOI 铁路处理货运。车站 2, 3, \ldots, N 有货 每个站都放置 1 。 位于 i (2 \leqq i \leqq N) 的货物价值为 A_i 。

IOI铁路运营货运列车 1 我拥有该组织。这列火车是第一站 1 并且可以在IOI铁路线上双向运行。在每个车站,您可以将储存在该车站的货物装载到火车上,或者将装载到火车上的货物卸下并留在该车站。

使用该货运列车的车站 2, 3, \ldots, N 我想把它运送到 1 。不过,这列火车不运载货物。 您只能发布 W 或更少。也就是说,任何时候列车上都没有货物。 不允许列出超过 W + 1 。此外,由于燃料限制,该列车的最大总里程为 D 只能运行。因此,所有货物都被送往车站。 可能无法将其传送到 1 。

IOI铁路社长JOI君希望,在这种情况下,通过适当地运行货运列车,他最终能够到达车站。 我想尽可能增加放置在 1 的货物的总价值。

当给出货运列车信息和各站存储的货物信息时,最终 编写一个程序来查找 1 中存储的货物值的最大可实现总和。

制約

  • 2 \leqq N \leqq 450.
  • 1 \leqq W \leqq N - 1.
  • 2 \leqq D \leqq N^2 - N.
  • 1 \leqq A_i \leqq 1\,000\,000 (2 \leqq i \leqq N).
  • 所有输入值都是整数。

小課題

  1. (6 点) W = 1,A_i = 1 (2 \leqq i \leqq N).
  2. (9 点) A_i = 1 (2 \leqq i \leqq N).
  3. (24 点) W = 1.
  4. (13 点) N \leqq 15.
  5. (24 点) N \leqq 50.
  6. (24 点)没有额外的限制。

入力

输入按以下格式给出。

N W D 
A_2 A_3 \cdots A_N

出力

终于站了 1 可实现的最大价值作为放置的货物价值的总和 1 行。


入力例 1

4 1 10
1 1 1

出力例 1

2

例如,如果您运行如下所示的货运列车,它最终会到达车站。 货物总价值位于 1 它可以是 2 。

首先,货运列车 我在 1 。

  1. 货运列车在车站 运行 2 。 置于
  2. 駅 2 上的值 将 1 货物装载到货运列车上。
  3. 货运列车在车站 运行 1 。 置于
  4. 货运列车装载的价值 1 货运到站 将其放入 1 。
  5. 货运列车在车站 运行 4 。 置于
  6. 駅 4 上的值 将 1 货物装载到货运列车上。
  7. 货运列车在车站 运行 1 。 置于
  8. 货运列车装载的价值 1 货运到站 将其放入 1 。

火车行驶的总距离为 8 火车的总距离是 10 满足车辆只能在以下行驶的条件。

这时,终于站了 位于 1 的货物总价值为 2 。终于到站了 由于它不能大于 1 它可以是 3 ,2 。

此输入示例满足所有子任务约束。


入力例 2

7 3 16
1 1 1 1 1 1

出力例 2

5

例如,如果您运行如下所示的货运列车,它最终会到达车站。 货物总价值位于 1 它可以是 5 。

首先,货运列车 我在 1 。

  1. 货运列车在车站 运行 5 。 置于
  2. 駅 5 上的值 将 1 货物装载到货运列车上。
  3. 货运列车在车站 运行 6 。 置于
  4. 駅 6 上的值 将 1 货物装载到货运列车上。
  5. 货运列车在车站 运行 1 。 置于
  6. 装载在货运列车上 2 值 所有 1 货物到站 1 。
  7. 货运列车在车站 运行 2 。 置于
  8. 駅 2 上的值 将 1 货物装载到货运列车上。
  9. 货运列车在车站 运行 3 。 置于
  10. 駅 3 上的值 将 1 货物装载到货运列车上。
  11. 货运列车在车站 运行 4 。 置于
  12. 駅 4 上的值 将 1 货物装载到货运列车上。
  13. 货运列车在车站 运行 1 。 置于
  14. 装载在货运列车上 3 值 所有 1 货物到站 1 。

火车行驶的总距离为 16 火车的总距离是 16 满足车辆只能在以下行驶的条件。

这时,终于站了 位于 1 的货物总价值为 5 。终于到站了 由于它不能大于 1 它可以是 6 ,5 。

此输入示例是一个小作业。 2, 4, 5, 6 满足约束。 在


入力例 3

5 2 12
40 30 20 10

出力例 3

100

例如,如果您运行如下所示的货运列车,它最终会到达车站。 货物总价值位于 1 它可以是 100 。

首先,货运列车 我在 1 。

  1. 货运列车在车站 运行 5 。 置于
  2. 駅 5 上的值 将 10 货物装载到货运列车上。
  3. 货运列车在车站 运行 4 上运行。
  4. 駅 4 上的值 将 20 货物装载到货运列车上。
  5. 货运列车在车站 运行 2 。 置于
  6. 货运列车装载的价值 10 运费和价值 20 货运到站 将其放入 2 。
  7. 駅 2 上的值 将 40 货物装载到货运列车上。
  8. 货运列车在车站 运行 3 。 置于
  9. 駅 3 上的值 将 30 货物装载到货运列车上。
  10. 货运列车在车站 运行 1 。 置于
  11. 货运列车装载的价值 30 运费和价值 40 货运到站 将其放入 1 。
  12. 货运列车在车站 运行 2 。 置于
  13. 駅 2 上的值 将 10 运费和价值 20 货物装载到货运列车上。
  14. 货运列车在车站 运行 1 。 置于
  15. 货运列车装载的价值 10 运费和价值 20 货运到站 将其放入 1 。

火车行驶的总距离为 12 火车的总距离是 12 满足车辆只能在以下行驶的条件。

这时,终于站了 位于 1 的货物总价值为 100 。终于到站了 由于它不能大于 1 它可以是 101 ,100 。

此输入示例是一个小作业。 4, 5, 6 满足约束。 在


入力例 4

5 1 11
2 7 1 8

出力例 4

10

此输入示例是一个小作业。 3, 4, 5, 6 满足约束。 在


入力例 5

9 3 14
54640 754112 604290 105866 591907 801383 502975 379373

出力例 5

2214425

此输入示例是一个小作业。 4, 5, 6 满足约束。 在