刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

毕业旅行

时间限制：1s

内存限制：128MB

（注：input()括号中不允许添加任何提示语）

小王要从一个城市出发前往另一个城市进行一场毕业旅行，在此期间会经过m（1≤m≤100）个中转城市。小王给每个城市按顺序设置了一个对他们的喜爱度，分别用a1,a2, ...,am（1≤ ≤100）表示，不同的城市可能拥有相同的喜爱度。现在，小王需要选择k（1≤k≤m）个编号连在一起的中转城市作为重点游览的城市，并希望重点游览的城市喜爱度之和最大。

请编写一段程序，计算并输出小王重点游览的城市喜爱度之和可以获得的最大值。

输入描述：

第一行依次输入两个正整数m和k，依次表示会经过的中转城市数量和重点游览城市数量，正整数之间以空格隔开

第二行依次输入m个正整数，依次表示每个城市的喜爱度 ，正整数之间以空格隔开

输出描述：

输出一个整数，表示小王重点游览的城市喜爱度之和可以获得的最大值


输入样例：

4 2
10 20 15 30

输出样例：

45

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythonm, k = map(int, input().split())cities = list(map(int, input().split()))dp = [0] * (m + 1)for i in range(1, m + 1):dp[i] = dp[i - 1]for j in range(max(0, i - k + 1), i):dp[i] = max(dp[i], dp[j] + cities[j - 1] * (i - j + 1))print(dp[m])```

解析：

【喵呜刷题小喵解析】：
本题是一道典型的动态规划问题，可以使用动态规划来解决。
首先，定义状态转移方程。令 dp[i] 表示选取前 i 个城市时，能够获得的最大喜爱度之和。则对于每一个 i，都有两种可能，选取或者不选取第 i 个城市。如果不选取第 i 个城市，那么 dp[i] = dp[i-1]。如果选取第 i 个城市，那么 dp[i] = dp[j] + cities[j] * (i - j)，其中 j 是从 i-k 到 i-1 中的一个城市。因为题目要求选取 k 个编号连在一起的城市，所以 j 的取值范围是从 i-k 到 i-1。
然后，遍历所有的城市，更新 dp 数组。最后，输出 dp[m]，即选取前 m 个城市时，能够获得的最大喜爱度之和。

具体实现时，可以使用一个一维数组 dp 来保存状态转移方程的结果。在遍历城市时，对于每一个城市 i，都遍历从 i-k 到 i-1 的所有城市 j，更新 dp[i]。最后，输出 dp[m] 即可。

注意，题目中要求 input() 括号中不允许添加任何提示语，所以在输入时，需要使用空格作为分隔符，将输入的两个整数和 m 个城市的喜爱度分别读入到变量 m、k 和 cities 中。
创作类型：
原创

本文链接：毕业旅行 时间限制：1s 内存限制：128MB （注：input()括号中不允许添加任何提示语） 小

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share