题解 | 放它一马

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    long long maxGrade = 0;
  	// （击败怪物数%10 + 1）作为a[i]系数影响杀怪的最终奖励，系数 j 取值范围只有 0 ~ 9 
    // dp[i][j] 遇到第i个怪物时，在系数j下可以获得的最大奖励
    vector<vector<long long>> dp(n + 1, vector<long long>(10, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= 9 && j <= i; ++j) {

            dp[i][j] =  max(dp[i - 1][j] + i, dp[i][j]); // 不杀怪

            int prev = (j == 0) ?  9 : j - 1;

            long long temp = ( i <= 9 && j == 0) ? 0 : dp[i - 1][prev] + a[i] * (j + 1);
            dp[i][j] = max(temp, dp[i][j]); // 杀怪，当i不超过9的时候，不可能出现 j = 0（最少杀十个冤大头才会出现 j = 0 的情况 ），不能增加奖励

            maxGrade = max(maxGrade, dp[i][j]);
        }
    }
    cout << maxGrade << endl;
}

一、解题思路

1、不杀怪奖励 i, 杀怪奖励 a[i]*( count mod 10 + 1)

2、为什么每一步都贪心，取奖励最大值不行？

考虑极端情况:

数组a长度为11(包含十个小怪物) ,a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10000] (0想象成哨兵，为了使索引和击杀怪物数量对应，无实际用途)，这种情况下前9次按照贪心思路，显然应该给它们全杀喽！！！那么杀死第十个倒霉蛋的时候 10 mod 10 = 0，杀怪奖励为 a[i] = 10000, 如果前面积攒一个功德，让生命值为10000的倒霉蛋第九个死，杀怪奖励显然为 10 * a[i] , 奖励翻十倍！！！

3、dp设计思路，及递推公式

（1）状态：第i个小怪兽，j杀怪奖励的系数（mod完后取0 ~ 9，可以想象成攒大招）

dp[i][j] 遇到第i个怪物时，在系数j下可以获得的最大奖励（如果杀）

（2）递推公式：

不杀怪时：max(dp[i - 1][j] + i, dp[i][j]) 参照遇见前 i - 1 个怪物在系数j下的最大奖励

杀怪时：max(dp[i - 1][prev] + a[i] * (j + 1) , dp[i][j]) 参照遇见前 i - 1 个怪物在前一个系数为（prev = j - 1 或 9）下的最大奖励

注意当i <= 9的时候不可能出现“已经杀死十个倒霉蛋”的状况，所以此时的杀怪奖励应该为0（之前没处理这里，和系统一顿抢分，导致每次输出值都比测试用例的大，哈哈~~~）。

初始化dp数组的大小为（ n + 1, 10），第一行初始化为0，理解为没遇见怪物前，不管有多少大招都没有奖励值。