题解 | 放它一马

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

int main() {
    int n;
    cin >> n;
    vector<int64> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // dp[r]：处理到当前右侧（初始为 n+1），已击败数量 mod 10 = r 的最优值
    array<int64, 10> dp{}; // 初始全 0，表示 i = n+1 时的边界
    for (int i = n; i >= 1; --i) {
        array<int64, 10> ndp{};
        for (int r = 0; r < 10; ++r) {
            // 选择放走
            int64 keep = i + dp[r];
            // 选择击败（这是第 r+1 次击败）
            int nr = (r + 1) % 10;
            int64 beat = a[i] * (1 + nr) + dp[nr];
            ndp[r] = max(keep, beat);
        }
        dp = ndp;
    }
    cout << dp[0] << '\n'; // 初始已击败 0 个
    return 0;
}