P14300 [JOI2023 预选赛 R2] 货物列车 / Freight Train

IOI 铁路运营着一条铁路线。该铁路线上有 $N$ 个车站，沿直线依次排列，编号从 $1$ 到 $N$。对于每个 $i$（$1 \le i \le N-1$），车站 $i$ 与车站 $i+1$ 之间由一条长度为 $1$ 的线路连接。 IOI 铁路负责货物运输。在车站 $2, 3, \cdots, N$ 上各放置一件货物，车站 $i$（$2 \le i \le N$）上货物的价值为 $A_i$。 IOI 铁路拥有一列货运列车。该列车初始位于车站 $1$，可在 IOI 铁路线路上双向行驶。在每个车站，列车可以装载该站放置的货物，也可以卸下已装载的货物，或将货物留在该站。 现计划使用该货运列车，将车站 $2, 3, \cdots, N$ 上的货物运送到车站 $1$。但该列车最多只能装载 $W$ 件货物，即在任何时刻，列车上装载的货物数量不得超过 $W$ 件。此外，由于燃料限制，列车最多只能行驶总距离 $D$。因此，可能无法将所有货物运送到车站 $1$。 作为 IOI 铁路社长的 JOI 君，希望在满足上述条件的前提下，合理调度货运列车，使得最终在车站 $1$ 上的货物总价值尽可能大。 给定货运列车的信息以及各站货物的信息，编写一个程序，求出最终在车站 $1$ 上的货物总价值所能达到的最大值。

输入数据按以下格式给出： $N\ W\ D$ $A_2\ A_3\ \cdots\ A_N$

在一行内输出最终在车站 $1$ 上的货物总价值所能达到的最大值。

### 样例 1 解释 例如，若按以下方式运行货运列车，最终可在车站 $1$ 上获得总价值为 $2$ 的货物： 初始时，货运列车位于车站 $1$。 - 将列车驶向车站 $2$。 - 装载车站 $2$ 上价值为 $1$ 的货物。 - 将列车驶回车站 $1$。 - 将列车上价值为 $1$ 的货物卸至车站 $1$。 - 将列车驶向车站 $4$。 - 装载车站 $4$ 上价值为 $1$ 的货物。 - 将列车驶回车站 $1$。 - 将列车上价值为 $1$ 的货物卸至车站 $1$。 列车行驶的总距离为 $8$，满足“列车最多只能行驶总距离 $10$”的限制条件。 此时，最终在车站 $1$ 上的货物总价值为 $2$。由于无法使车站 $1$ 上的货物总价值达到 $3$ 或以上，故应输出 $2$。 该输入样例满足所有子任务的约束。 ### 样例 2 解释 例如，若按以下方式运行货运列车，最终可在车站 $1$ 上获得总价值为 $5$ 的货物： 初始时，货运列车位于车站 $1$。 - 将列车驶向车站 $5$。 - 装载车站 $5$ 上价值为 $1$ 的货物。 - 将列车驶向车站 $6$。 - 装载车站 $6$ 上价值为 $1$ 的货物。 - 将列车驶回车站 $1$。 - 将列车上两个价值均为 $1$ 的货物全部卸至车站 $1$。 - 将列车驶向车站 $2$。 - 装载车站 $2$ 上价值为 $1$ 的货物。 - 将列车驶向车站 $3$。 - 装载车站 $3$ 上价值为 $1$ 的货物。 - 将列车驶向车站 $4$。 - 装载车站 $4$ 上价值为 $1$ 的货物。 - 将列车驶回车站 $1$。 - 将列车上三个价值均为 $1$ 的货物全部卸至车站 $1$。 列车行驶的总距离为 $16$，满足“列车最多只能行驶总距离 $16$”的限制条件。 此时，最终在车站 $1$ 上的货物总价值为 $5$。由于无法使车站 $1$ 上的货物总价值达到 $6$ 或以上，故应输出 $5$。 该输入样例满足子任务 2、4、5、6 的约束。 ### 样例 3 解释 例如，若按以下方式运行货运列车，最终可在车站 $1$ 上获得总价值为 $100$ 的货物： 初始时，货运列车位于车站 $1$。 - 将列车驶向车站 $5$。 - 装载车站 $5$ 上价值为 $10$ 的货物。 - 将列车驶向车站 $4$。 - 装载车站 $4$ 上价值为 $20$ 的货物。 - 将列车驶向车站 $2$。 - 将列车上价值为 $10$ 和 $20$ 的货物卸至车站 $2$。 - 装载车站 $2$ 上价值为 $40$ 的货物。 - 将列车驶向车站 $3$。 - 装载车站 $3$ 上价值为 $30$ 的货物。 - 将列车驶回车站 $1$。 - 将列车上价值为 $30$ 和 $40$ 的货物卸至车站 $1$。 - 将列车驶向车站 $2$。 - 装载车站 $2$ 上价值为 $10$ 和 $20$ 的货物。 - 将列车驶回车站 $1$。 - 将列车上价值为 $10$ 和 $20$ 的货物卸至车站 $1$。 列车行驶的总距离为 $12$，满足“列车最多只能行驶总距离 $12$”的限制条件。 此时，最终在车站 $1$ 上的货物总价值为 $100$。由于无法使车站 $1$ 上的货物总价值达到 $101$ 或以上，故应输出 $100$。 该输入样例满足子任务 4、5、6 的约束。 ### 数据范围 - $2 \le N \le 450$。 - $1 \le W \le N - 1$。 - $2 \le D \le N^2 - N$。 - $1 \le A_i \le 1\,000\,000$（$2 \le i \le N$）。 - 所有输入值均为整数。 ### 子任务 1. （6 分）$W = 1$，且 $A_i = 1$（$2 \le i \le N$）。 2. （9 分）$A_i = 1$（$2 \le i \le N$）。 3. （24 分）$W = 1$。 4. （13 分）$N \le 15$。 5. （24 分）$N \le 50$。 6. （24 分）无额外约束。 翻译由 Qwen3-235B 完成。