上海计算机学会2020年7月月赛C++乙组T1跑步
发布时间
阅读量：
阅读量
为了找到小爱在比赛中的最优策略以最大化得分，我们可以使用动态规划方法来解决这个问题。通过分析每种选择对后续选项的影响和限制条件下的最优解路径变化规律和趋势特征等信息进行建模和求解。
方法思路
我们使用动态规划来解决这个问题，并且只保留前一阶段的状态信息以优化空间复杂度。具体步骤如下：
状态定义
设 dp 数组记录各阶段的最大得分：
`
dp[run]: 当前路段选择跑步时的最大得分；
dp[stay]: 当前路段选择
题目描述
小爱正在参与一场跑步比赛，在整个赛程划分为若干个路段的情况下进行角逐。其中每个路段的得分为ai，在每一阶段上她都可以选择进行跑步、快速冲刺或散步等不同的运动方式，并且每项选择对应的得分也不同。
- 若决定在某段路程上进行跑步，则可以获得 ai 分；
- 若某段路程采用突袭策略，则得分会翻倍（变为双倍的 ai 分），但需注意后续路段的速度必须放慢；
- 若某段路程以慢速行进，则将不得分。
小爱在每段路上应该如何选择，才能使得分之和最大呢？
输入格式
第一行：单个整数 n。
第二行：n 个整数表示 a1 到 an。
输出格式
单个整数：表示答案。
数据范围
- 对于 30% 的数据，1≤n≤100；
- 对于 60% 的数据，1≤n≤1000；
- 对于 100% 的数据，1≤n≤100000；1≤ai≤10000。
样例数据
输入:
4
1 2 3 4
输出:
14
说明:
前几段都正常跑步，最后一段突击，得分为1+2+3+4*2
采用递归计算的方式进行动态规划求解
详见代码：
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int k[100005];
int z[100005];
int m[100005];
int main() {
int n;
int ans;
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
k[i] = max(z[i - 1], m[i - 1]) + 2 * a[i];//快跑取上一段慢跑和走的最大值+2*ai
z[i] = max(max(k[i - 1], z[i - 1]), m[i - 1]);//走取上一段三种状态的最大值
m[i] = max(m[i - 1], z[i - 1]) + a[i];//慢跑取上一段走和慢跑的最大值+ai
}
ans = max(max(k[n], z[n]), m[n]);//答案是三种状态的最大值
cout << ans << endl;
return 0;
}全部评论 (0)
还没有任何评论哟~