侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 28 条评论

目 录CONTENT

文章目录

【线性DP】闯关

GabrielxD
2023-04-15 / 0 评论 / 0 点赞 / 388 阅读 / 544 字
温馨提示:
本文最后更新于 2023-04-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

试题 算法提高 闯关


这个游戏有 nn 个关卡,第 ii 个关卡你可以得到 V[i]V[i] 的金钱。但是每打一个关卡就会损失 PP 的金钱。

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

你必须从第 11 关打起,问你打完第 nn 个关卡时最多可以得到多少金钱?

输入

第一行 n,m,Pn, m, P

第二行 nn 个整数 V[i]V[i]

输出

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

样例输入

2 2 2
1 2

样例输出

-1

数据规模和约定

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

解题

方法一:动态规划

思路

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

动态规划:

  • 状态定义: f[i]f[i] 表示所有打到第 ii 个关卡的策略中能得到的最多金钱;
  • 状态转移: f[i]=max(f[i],f[j]+v[i]p),j=max(1,im)i1f[i] = \max(f[i], f[j] + v[i] - p), \enspace j = \max(1, i - m) \dots i - 1
  • 初始状态: f[1]=v[i]pf[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]);
    }
}
0

评论区