题目链接

放它一马

题目描述

小美按顺序遇到 只怪物（编号为 ），第 只怪物的生命值为 。对于每只怪物，小美有两个选择：

  1. 放走：获得 点经验值。
  2. 击败：获得 点基础经验值，并额外获得 点奖励经验值，其中 是到目前为止累计击败的怪物总数（包括当前这只）。

请求出小美在处理完所有 只怪物后，能获得的最大总经验值。

解题思路

这是一个动态规划问题。核心的观察点在于，击败怪物的额外收益仅仅取决于已击败怪物数量对10取模的余数，而不是击败怪物的确切总数。这个特性使得我们可以大大优化DP的状态表示。

1. DP状态定义

由于奖励只和击败数量的个位数有关，我们不需要记录完整的击败数量。 我们定义一个一维DP数组，大小为10： ：表示在考虑完若干怪物后，已击败的怪物总数模10的余数为 时，所能获得的最大经验值。

2. DP状态转移

我们按顺序遍历每只怪物。当我们考虑第 只怪物（生命值为 ）时，我们需要根据前一阶段的DP状态来计算当前阶段的新状态。为了避免在一次迭代中混淆新旧状态，我们使用一个临时数组 new_dp 来存储当前阶段的结果。

假设我们已经处理完前 只怪物，dp 数组存储着对应的最大经验值。现在我们来处理第 只怪物：

遍历前一阶段的所有可能状态 j from 0 to 9（即击败了 只怪物，且 ）：

  • 如果 dp[j] 是一个可达状态（即经验值有效），我们基于这个状态做决策：

    1. 决策一：放走第 只怪物。

      • 击败数不变，所以模10的余数仍然是 。
      • 获得的经验是在原有基础上增加 。
      • 我们可以用 dp[j] + i 这个值去更新 new_dp[j]。

    2. 决策二：击败第 只怪物。

      • 击败数从 变为 。新的模10余数是 (j + 1) % 10。
      • 这是第 只被击败的怪物，所以奖励乘数是 。
      • 获得的经验是在 dp[j] 基础上增加 。
      • 我们用这个值去更新 new_dp[(j + 1) % 10]。

  • 迭代完所有的 j 后，new_dp 就包含了处理完第 只怪物后的所有状态。我们将其复制回 dp 数组，进行下一轮迭代。

3. 初始化和最终答案

  • 初始化：在遇到第一只怪物之前，我们击败了0只怪物，经验为0。所以 dp[0] = 0，而其他状态 dp[1...9] 都是不可达的，可以初始化为一个极小值（或-1，因为经验值非负）。
  • 最终答案：在处理完所有 只怪物后，dp 数组中的最大值就是我们所求的最大总经验。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // dp[j] 表示击败怪物数 mod 10 = j 时的最大经验
    vector<long long> dp(10, -1);
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        vector<long long> new_dp = dp;
        for (int j = 0; j < 10; ++j) {
            if (dp[j] == -1) continue; // 跳过不可达状态

            // 决策1: 放走第 i+1 只怪物
            long long pass_exp = dp[j] + (i + 1);
            new_dp[j] = max(new_dp[j], pass_exp);

            // 决策2: 击败第 i+1 只怪物
            int next_mod = (j + 1) % 10;
            long long defeat_exp = dp[j] + a[i] * (1 + next_mod);
            new_dp[next_mod] = max(new_dp[next_mod], defeat_exp);
        }
        dp = new_dp;
    }

    long long max_exp = 0;
    for (int j = 0; j < 10; ++j) {
        max_exp = max(max_exp, dp[j]);
    }

    cout << max_exp << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        // dp[j] 表示击败怪物数 mod 10 = j 时的最大经验
        long[] dp = new long[10];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            long[] newDp = dp.clone();
            for (int j = 0; j < 10; j++) {
                if (dp[j] == -1) continue; // 跳过不可达状态

                // 决策1: 放走第 i+1 只怪物
                long passExp = dp[j] + (i + 1);
                newDp[j] = Math.max(newDp[j], passExp);

                // 决策2: 击败第 i+1 只怪物
                int nextMod = (j + 1) % 10;
                long defeatExp = dp[j] + a[i] * (1 + nextMod);
                newDp[nextMod] = Math.max(newDp[nextMod], defeatExp);
            }
            dp = newDp;
        }

        long maxExp = 0;
        for (long exp : dp) {
            maxExp = Math.max(maxExp, exp);
        }

        System.out.println(maxExp);
    }
}

n = int(input())
a = list(map(int, input().split()))

# dp[j] 表示击败怪物数 mod 10 = j 时的最大经验
dp = [-1] * 10
dp[0] = 0

for i in range(n):
    new_dp = dp[:]
    for j in range(10):
        if dp[j] == -1:
            continue

        # 决策1: 放走第 i+1 只怪物
        pass_exp = dp[j] + (i + 1)
        new_dp[j] = max(new_dp[j], pass_exp)

        # 决策2: 击败第 i+1 只怪物
        next_mod = (j + 1) % 10
        defeat_exp = dp[j] + a[i] * (1 + next_mod)
        new_dp[next_mod] = max(new_dp[next_mod], defeat_exp)
    
    dp = new_dp
        
print(max(dp))

算法及复杂度

  • 算法：动态规划
  • 时间复杂度：。我们遍历 个怪物，每次遍历更新大小为10的DP数组，总操作次数与 成正比。
  • 空间复杂度：。DP数组的大小是常数10。