【每日一题】Max Power

Max Power

https://ac.nowcoder.com/acm/problem/20663

题目

题目描述：
小卤蛋刚把dnf的技能点重新洗了一遍,现在他要重新加点,假设他的技能树一共有n层，第i层有n-i+1个
技能，每个技能只能够学习一次。除了第1层的技能可以直接学习外，其他技能学习都要学习前置技能，
即你要学习第i(i>=2)层第j列的技能，那么你要先学习第i-1层的第j列和第j+1列的技能。每个技能学习
后都会获得一定的战力加成。
现在小卤蛋有m个技能点，一个技能点可以学习一个技能，他想知道加完点后他可以获得的最大战力加成为多少。

输入描述：
有多组样例输入，输入到文件结束。
每组样例第一行输入2个整数n(1<=n<=50)和m(1<=m<=1300)，对应题目上的含义。
接下来共有n行，第i行有n-i+1个数，代表这个技能学习后获得的战力加成(战力加成<=1000)。

输出描述：

输出最大的战力加成。

解析

1）知识点

这道题是显而易见的动态规划，但我不会写而已。

2）看题目

题目的意思是，我们有一颗倒三角技能树，要学某个技能一定要学自己上面和右上面的技能，一个技能一个技能点，求最大伤害加成。

3）算法分析

既然我们都能看出来这道题是一个dp了，那么首先就是：动态规划最重要的就是递推和dp数组的含义。
那么首先我们来看dp数组：
1. 按照惯例，我们先看这道题有哪些重要的数据。
2. 因为这道题藏得有点深，我们要先推理一下：
  1. 首先我们知道，如果我们要学一个技能，一定要学完一个倒三角：
  2. 所以在这里我们就知道了我们某一点的行列时很重要的，但是我们的选择不一定这么规律就是一个倒三角：
  3. 这个时候我们就要进行枚举，将所有可能性算出来（指蓝色的区域），但是这个区域计算也是有限制的，限制就是我们的技能点数（不能超了）。
3. 综上所述，重要的数据有有三个，关键点选取的行列，然后就是使用的技能点数。就可以做成一个三维dp使用了。
根据上面的举例，我们也可以理解，为了得到以某一点（红色的点）为关键点，进行递推得到答案。
然后关键点是啥呢，就是最左边最下面的点，以ta作为边界标志。
接下来就是递推了呢：
1. 递推怎么来呢？我们还是用这张图来推理一下：
  1. 首先我们可以发现，每一列的选取范围一定连续，说到这，为了节省时间，是不是一下就能想到前缀和了呢。所以我们做一个二维列前缀和。
  2. 接下来如果要进行计算数量，我们只要每次向后一列，列数减一，用前缀和就可以得到倒三角了。
  3. 但是我们要用掉技能点，所以肯定要进行枚举，也就是判断多出来了哪些蓝***域。所以我们加一个循环用于遍历猜测。
2. 所以我们的递推就是，先两层循环确定关键点位置，然后第三层循环枚举消耗掉的技能点数，最少为倒三角大小，最大为输入值。
3. 最后加一层循环用于蓝***间的猜想遍历。
4. 说了这么多，其实遍历就是不停的往下一列加起来罢了：dp[i][j][k] = max(dp[i][j][k], dp[i-1][l][k-j] + sum[i][j])。（i，j，k，l分别为四层循环的变量）

4）算法操作

我们还是依旧先看一下我们的dp数组（原因结合算法分析中的介绍）：
```
int dp[N][N][M];//dp[第i列][选了前j个][一共选了k个] = 最大战力加成
```

然后我们按分析的来得到用于遍历的循环：

首先是关键点的位置：

for (int i = n; i >= 1; i--) //枚举列
        for (int j = 0; j <= n - i + 1; j++) //枚举选取前j行

然后是花费的技能点数：

for (int k = mn[j]; k <= m; k++) //枚举所花的技能点数

最后就是循环进行猜想蓝***域（倒三角外附加的）了：

for (int l = max(0, j - 1); l < n - i + 1; l++) {//枚举下一列有多少个（一定比j-1大）

最后就是我们的递推公式了吧：

dp[i][j][k] = max(dp[i][j][k], dp[i + 1][l][k - j] + sum[j][i]);

5）打代码

打代码咯！
dp的过程其实都很简单，重点都在思路。
就是输入，然后循环进行动态规划。
看我代码咯~

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int N = 50 + 7;
const int M = 1300 + 7;
int n, m;//n表示技能树大小，m表示技能点数
int sum[N][N];//前缀和数组，表示sum[第i列][前j个]
int dp[N][N][M];//dp[第i列][选了前j个][一共选了k个] = 最大战力加成
int mn[N];//mn[i]表示到达第i层最少要用的技能点数
//全局变量区

int main() {
    IOS;
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++) {
            mn[i] = mn[i - 1] + i;
            for (int j = 1; j <= n - i + 1; j++) {
                cin >> sum[i][j];
                sum[i][j] += sum[i - 1][j];
            }
        }
        //输入

        int ans = 0;
        memset(dp, 0, sizeof dp);
        for (int i = n; i >= 1; i--) {//枚举列
            for (int j = 0; j <= n - i + 1; j++) {//枚举选取前j行
                for (int k = mn[j]; k <= m; k++) {//枚举所花的技能点数
                    for (int l = max(0, j - 1); l < n - i + 1; l++) {//枚举下一列有多少个（一定比j-1大）
                        dp[i][j][k] = max(dp[i][j][k], dp[i + 1][l][k - j] + sum[j][i]);
                    }
                    ans = max(ans, dp[i][j][m]);
                }
            }
        }
        //递推

        cout << ans << endl;
        //输出
    }
    return 0;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏