题目
这个游戏有 个关卡,第 个关卡你可以得到 的金钱。但是每打一个关卡就会损失 的金钱。
当你打完第 个关卡的时候,可以选择打第 个关卡。
你必须从第 关打起,问你打完第 个关卡时最多可以得到多少金钱?
输入
第一行 。
第二行 个整数 。
输出
输出一行表示最多可以获得的金钱。
样例输入
2 2 2
1 2
样例输出
-1
数据规模和约定
- 其余所有数字都是不超过 的非负整数
解题
方法一:动态规划
思路
类似动态规划入门题「爬楼梯问题」的升级版,每次可以走 阶楼梯。
动态规划:
- 状态定义: 表示所有打到第 个关卡的策略中能得到的最多金钱;
- 状态转移: ;
- 初始状态: 。
代码
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken(); int n = (int) in.nval;
in.nextToken(); int m = (int) in.nval;
in.nextToken(); int p = (int) in.nval;
int[] v = new int[n + 1];
for (int i = 1; i <= n; ++i) {
in.nextToken(); v[i] = (int) in.nval;
}
long[] f = new long[n + 1];
f[1] = v[1] - p;
for (int i = 2; i <= n; ++i) {
f[i] = Long.MIN_VALUE;
for (int j = Math.max(1, i - m); j < i; ++j) {
f[i] = Math.max(f[i], f[j] + v[i] - p);
}
}
System.out.println(f[n]);
}
}
评论区