题解 | 放它一马

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] nums = new long[n];
        for(int i = 0; i < n; i++){
            nums[i] = in.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] + nums[i] * (1 + nextMod);
                newDp[nextMod] = Math.max(newDp[nextMod], defeatExp);
            }
            dp = newDp;
        }
        long maxExp = 0;
        for(long exp : dp){
            maxExp = Math.max(exp, maxExp);
        }
        System.out.println(maxExp);
    }
}