【每日一题】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数组：
- 按照惯例，我们先看这道题有哪些重要的数据。
- 因为这道题藏得有点深，我们要先推理一下：
- 首先我们知道，如果我们要学一个技能，一定要学完一个倒三角：
- 所以在这里我们就知道了我们某一点的行列时很重要的，但是我们的选择不一定这么规律就是一个倒三角：
- 这个时候我们就要进行枚举，将所有可能性算出来（指蓝色的区域），但是这个区域计算也是有限制的，限制就是我们的技能点数（不能超了）。
- 首先我们知道，如果我们要学一个技能，一定要学完一个倒三角：
- 综上所述，重要的数据有有三个，关键点选取的行列，然后就是使用的技能点数。就可以做成一个三维dp使用了。
- 根据上面的举例，我们也可以理解，为了得到以某一点（红色的点）为关键点，进行递推得到答案。
- 然后关键点是啥呢，就是最左边最下面的点，以ta作为边界标志。
- 接下来就是递推了呢：
- 递推怎么来呢？我们还是用这张图来推理一下：
- 首先我们可以发现，每一列的选取范围一定连续，说到这，为了节省时间，是不是一下就能想到前缀和了呢。所以我们做一个二维列前缀和。
- 接下来如果要进行计算数量，我们只要每次向后一列，列数减一，用前缀和就可以得到倒三角了。
- 但是我们要用掉技能点，所以肯定要进行枚举，也就是判断多出来了哪些蓝***域。所以我们加一个循环用于遍历猜测。
- 所以我们的递推就是，先两层循环确定关键点位置，然后第三层循环枚举消耗掉的技能点数，最少为倒三角大小，最大为输入值。
- 最后加一层循环用于蓝***间的猜想遍历。
- 说了这么多，其实遍历就是不停的往下一列加起来罢了：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;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
开发本科够了，早准备早投递
投递牛客等公司10个岗位 >
