思路概述

击败第 i 只怪物的额外加成只与“已击败数量对 10 取模”有关，而与具体击败了谁、击败了多少整十无关。因此可用动态规划，把“已击败数量 mod 10”作为状态，线性推进。

状态设计

令 dp[m] 表示在处理完当前怪物之前，已击败数量 ≡ m (mod 10) 时能获得的最大经验值（滚动数组维护上一只怪物处理后的状态）。

转移

处理第 i 只怪物、生命为 a_i：

• 放走：ndp[m] = max(ndp[m], dp[m] + i)
• 击败：新的余数 nm = (m + 1) % 10，收益 gain = a_i * (1 + nm)，转移 ndp[nm] = max(ndp[nm], dp[m] + gain)

初始：dp[0] = 0，其余为 -∞。答案为处理完 n 只后 max(dp)。

正确性说明

• 任何时刻，未来每次“击败”只会把已击败数量模 10 增加 1，且本次收益只取决于新的余数 nm 与 a_i，与具体击败了多少整十（10、20、…）无关。
• 因此，以“已击败数 mod 10”为充分状态即可，不会丢失决策必要信息。线性 DP 枚举两种选择覆盖了所有方案，取最大值即为最优。

实现细节

• 负无穷使用一个足够小的常量，如 -9e18（Java/C++）或 -10**30（Python）。
• i 必须是题目原编号（1 开始），用于“放走”收益。
• 每步先拷贝/重置 ndp，完成两类转移后覆盖 dp。

复杂度分析

• 状态数恒为 10，每个怪物转移 10 个状态：时间复杂度 O(10n) = O(n)；
• 仅用两个长度为 10 的数组滚动：空间复杂度 O(10) = O(1)。
• 注意使用 64 位整型（Python int / Java long / C++ long long）。

代码

Python

import sys

def solve():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    n = data[0]
    a = data[1:]

    INF = -10**30
    dp = [INF] * 10
    dp[0] = 0  # 初始击败数为 0（模 10 为 0）

    for i, val in enumerate(a, start=1):
        ndp = [INF] * 10
        for m in range(10):
            if dp[m] == INF:
                continue
            # 放走：已击败数模不变
            if dp[m] + i > ndp[m]:
                ndp[m] = dp[m] + i
            # 击败：模数 +1
            nm = (m + 1) % 10
            gain = val * (1 + nm)  # a_i * (1 + ((k+1) mod 10))
            v = dp[m] + gain
            if v > ndp[nm]:
                ndp[nm] = v
        dp = ndp

    print(max(dp))

if __name__ == "__main__":
    solve()

Java

import java.util.*;

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();

        // 负无穷：选个足够小的值，避免后续加法溢出
        long NEG = Long.MIN_VALUE / 4;

        // dp[m]：到当前为止，已击败数 ≡ m (mod 10) 的最大经验值
        long[] dp = new long[10];
        Arrays.fill(dp, NEG);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            long[] ndp = new long[10];
            Arrays.fill(ndp, NEG);

            for (int m = 0; m < 10; m++) {
                if (dp[m] == NEG) continue;

                // 选择放走第 i+1 只怪：已击败数模不变，收益 + (i+1)
                ndp[m] = Math.max(ndp[m], dp[m] + (long)(i + 1));

                // 选择击败第 i+1 只怪：模数 +1，收益 a[i] * (1 + ((m+1) mod 10))
                int nm = (m + 1) % 10;
                long gain = a[i] * (1 + nm);
                ndp[nm] = Math.max(ndp[nm], dp[m] + gain);
            }

            dp = ndp;
        }

        long ans = dp[0];
        for (int m = 1; m < 10; m++) ans = Math.max(ans, dp[m]);
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    const long long NEG = (long long)-9e18; // 负无穷
    long long dp[10], ndp[10];
    for (int m = 0; m < 10; ++m) dp[m] = NEG;
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int m = 0; m < 10; ++m) ndp[m] = NEG;
        for (int m = 0; m < 10; ++m) {
            if (dp[m] == NEG) continue;
            // 放走：加 i+1
            ndp[m] = max(ndp[m], dp[m] + (long long)(i + 1));
            // 击败：模 +1，收益 a_i * (1 + nm)
            int nm = (m + 1) % 10;
            long long gain = a[i] * (1 + nm);
            ndp[nm] = max(ndp[nm], dp[m] + gain);
        }
        for (int m = 0; m < 10; ++m) dp[m] = ndp[m];
    }

    long long ans = dp[0];
    for (int m = 1; m < 10; ++m) ans = max(ans, dp[m]);
    cout << ans << '\n';
    return 0;
}

题目内容

小美会按照编号从小到大的顺序依次遇到 $n$ 只怪物（编号为 $1$ ~ $n$），怪物 $i(1 ≤ i ≤ n)$ 的生命为 $a_i$ 。

对于每只怪物，小美都可以选择放走 Ta 或者击败 Ta。

• 如果放走怪物，小美将获得 $i$ 点经验值。

• 如果击败怪物，小美将获得 $a_i$ 点经验值，同时将额外获得 ($x$ $mod$ $10) × a_i$ 点经验值，$x$ 为击败怪物数量（包括这一个怪物）。

求小美最多可以从这 $n$ 个怪物中获得的经验值。

输入描述

第一行输入一个整数 $n(1 ≤ n ≤ 2 × 10^5)$ 表示怪物数。

第二行输入 $n$ 个整数 $a_i(1 ≤ a_i ≤ 10^9)$ 表示怪物的生命。

输出描述

输出一个整数表示小美可以获得最高的经验值。

样例1

输入

3
5 3 2

输出

27

说明

第一个怪物选择击败获得 $5+5×1= 10$ 的经验值，第二个怪物选择击败获得 $3+3×2= 9$ 的经验值，第三只怪物选择击败获得 $2+ 2×3=8$ 的经验值，总共获得 $27$ 的经验值。