【线性DP】闯关

题目

试题 算法提高 闯关

---

这个游戏有 $n$ 个关卡，第 $i$ 个关卡你可以得到 $V[i]$ 的金钱。但是每打一个关卡就会损失 $P$ 的金钱。

当你打完第 $i$ 个关卡的时候，可以选择打第 $i+1 \dots \min\{i+m,n\}$ 个关卡。

你必须从第 $1$ 关打起，问你打完第 $n$ 个关卡时最多可以得到多少金钱？

输入

第一行 $n, m, P$ 。

第二行 $n$ 个整数 $V[i]$ 。

输出

输出一行表示最多可以获得的金钱。

样例输入

2 2 2
1 2

样例输出

-1

数据规模和约定

• $0<m≤n≤1000$
• 其余所有数字都是不超过 $1,000,000,000$ 的非负整数

解题

方法一：动态规划

思路

类似动态规划入门题「爬楼梯问题」的升级版，每次可以走 $1 \sim m$ 阶楼梯。

动态规划：

• 状态定义： $f[i]$ 表示所有打到第 $i$ 个关卡的策略中能得到的最多金钱；
• 状态转移： $f[i] = \max(f[i], f[j] + v[i] - p), \enspace j = \max(1, i - m) \dots i - 1$ ；
• 初始状态： $f[1] = v[i] - p$ 。

代码

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]);
    }
}