【2018年宁波市小学组】汽车旅行

Question

我不会做
题目描述
小明想在暑假里自己开车回家，顺带进行短途的旅行，现在他有一辆油缸容量为L 单位的汽车，他的学校在 1 号点，家在 n 号点。把起点和终点计算在内，依次会经过 n 个城市。从第 i 号城市到 i+1 号城市需要消耗 Wi的油量，并且不能往回开（不能从 i+1 号城市开回到 i 号城市）。但是小明是个小机灵鬼，他发现每个城市的油价都不一样，这意味着需要有准备地规划自己应当在哪个城市加多少油。更有意思的是，他发现这 n 所城市都可以进行油价的自由买卖。在城市 i，如果每单位的购买油价为 Ci，那么每单位的售卖油价就为 0.95*Ci。当然小明不能太过于贪心，他只能把油放在油缸里，而不能放进瓶子或者罐子里，因为那样太危险。
现在小明有 m 单位的钱，请问到目的地最多还能够剩下多少钱？注意途中小明不能够欠钱！如果途中小明开不到终点，那么请输出-1。

输入
从文件 car.in 中读入数据。

输入一共有 3 行，第一行依次为 n（城市数量）, m（初始钱数）, L（油缸容量）。其中 n≤300，m≤10^9，L≤400。
第二行包含 n-1 个整数 Wi（1≤Wi≤400）。
第三行包含 n 个整数 Ci（1≤Ci≤10^9）。

输出
输出到文件 car.out 中。

输出共一行，保留两位小数，表示最后最多剩下多少钱。如果小明中途是在没有钱开回到家里，则输出-1。

样例输入 复制
样例输入1
3 100 12
5 5
9 20 10
样例输入2
3 100 5
5 5
9 100 10

样例输出 复制
样例输出1
20.00
样例输出2
-1

数据范围限制
对 30%的数据，n<8, L<8。
对 70%的数据，n<100, L<100。

提示
对于样例 1，在 1 号城市购买 11 升油消费 99，在 2 号城市卖掉 1 升， 盈利20*0.95=19，最终开到终点 3 号城市。所以最终剩下的钱数是 100-99+19=20

Answer 1

引自免费微信小程序：皆我百晓生

1. 理解题意

题目描述了小明想要自己开车回家，并进行短途旅行。他有一辆油缸容量为L的汽车，经过n个城市，从第i号城市到i+1号城市需要消耗Wi的油量。每个城市的油价都不一样，每单位购买油价为Ci，每单位售卖油价为0.95*Ci。现在小明有m单位的钱，请计算小明最终剩下多少钱。

2. 解题思路

我们可以采用动态规划的方法来解决这个问题。具体步骤如下：

• 定义一个二维数组dp[n+1][L+1]，其中dp[i][j]表示从城市1到城市i，油缸剩余容量为j时，所剩下的最大钱数。
• 初始化dp数组，将dp[i][0]（油缸容量为0时）初始化为负无穷，表示不可能到达该状态。
• 对于每个城市i，遍历油缸容量j（从1到L），计算从城市1到城市i的最大剩余钱数dp[i][j]。
  • 选择在城市i购买油：dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+c[i-1]-(j-w[i-1])*0.95)。其中dp[i-1][j-w[i-1]]表示从城市1到城市i-1，油缸剩余容量为j-w[i-1]时，所剩下的最大钱数，c[i-1]为第i-1个城市的油价，(j-w[i-1])*0.95表示购买油的花费。
  • 选择在城市i不购买油：dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]])。表示油缸剩余容量不变，不购买油，所剩下的最大钱数。
• 输出dp[n][L]，即表示从城市1到城市n，油缸剩余容量为L时，所剩下的最大钱数。

3. 代码实现