Max Power

题意：
小卤蛋刚把dnf的技能点重新洗了一遍,现在他要重新加点,假设他的技能树一共有n层，第i层有n-i+1个技能，每个技能只能够学习一次。除了第1层的技能可以直接学习外，其他技能学习都要学习前置技能，即你要学习第i(i>=2)层第j列的技能，那么你要先学习第i-1层的第j列和第j+1列的技能。每个技能学习后都会获得一定的战力加成。现在小卤蛋有m个技能点，一个技能点可以学习一个技能，他想知道加完点后他可以获得的最大战力加成为多少。
题解：
我们使用dp[i][j][k]学会了i j这个点及其右上角的技能花费了k个技能点的最大值。
因为如果我们想学会当前技能先，就要学会这个点他右上方所有点的技能，
因为如果你要学第i层j+1列的技能
那么你要先学习第i-1层的第j列和第j+1列的技能。
针对这个题这个要求，我们选择从右上角开始进行递推
先枚举列，再枚举相应的行。

代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string>
const int maxn = 60;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;

int dp[maxn][maxn][1310];
int f[maxn];
int a[maxn][maxn];
int main(){
    int n,m;
    for(int i=1;i<maxn;i++){
        f[i]=f[i-1]+i;
    }
    while(cin>>n>>m){
        memset(dp,0,sizeof dp);
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n-i+1;j++){
                int x;
                cin>>x;
                a[i][j]=x+a[i-1][j];
            }
        }
        int ans=0;
        for(int i=n;i;i--){
            for(int j=0;j<=n-i+1;j++){
                for(int k=f[j];k<=m;k++){
                    for(int p=max(0,j-1);p<n-i+1;p++){
                        dp[i][j][k]=max(dp[i][j][k],dp[i+1][p][k-j]+a[j][i]);
                    }
                }
                ans=max(ans,dp[i][j][m]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}