题目
题目描述:小卤蛋刚把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; } //函数区