【每日一题】Max Power 题解

Description

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

Solution

可以想象一下，对于一个点，如果能加点，那么如下图，以他为顶点往下延伸得到的直角三角形上所有点都需要加点

那么我们可以从右上角开始枚举，然后做dp，令

• 表示第i列第j行时剩下k点可加的最优答案

有状态转移方程 ;
其中 表示上一行可以转移的点

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;
const int mod = 9973;
int a[55][55];
ll dp[55][55][1305];
int num[55];
int main() {
  int n, m; 
  while(cin >> n >> m) {
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++) {
      num[i] = num[i - 1] + i;
      for(int j = 1; j <= n - i + 1; j++) {
        cin >> a[i][j];
        a[i][j] += a[i - 1][j];
      }
    }
    ll ans = 0;
    for(int i = n; i >= 1; i--) {
      for(int j = 0; j <= n - i + 1; j++) {
        for(int k = num[j]; k <= m; k++) {
          for(int l = max(0, j - 1); l < n - i + 1; l++) {
            dp[i][j][k] = max(dp[i][j][k], dp[i + 1][l][k - j] + a[j][i]);
          }
          ans = max(ans, dp[i][j][m]);
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}