题意

给出一个倒三角，点亮一个技能就会消耗一个技能点并且得到相应的技能值，但是除了第一行的技能可以直接消耗一个技能点点亮以外其他的都要点亮他正上方以及右上方的技能，给出三角形的规模和技能点数，要求获得的技能值最大，画个图理解

我要点亮技能值为5的那个技能就要点亮他上方（技能值为一）和右上方（技能值为9的）两个点

解析

首先我们用$mp[i][j]$来储存每个点的技能值，因为用到了第i行的前的每一行都要用到，所以我们可以直接用前缀和表示这一列的和

我们用数组表示学习到处，花费了个技能点的最大收益

很容易就能想到枚举列数，从最右边开始枚举，然后枚举行数，表示学到当前前一列的某个技能的情况下，然后枚举技能点数，枚举到m最大，最后枚举决策点，是从j−1到当前最底下的任意一点。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=57;
const int MAXM=1307;

int f[MAXN];
int mp[MAXN][MAXN];
int dp[MAXN][MAXN][MAXM];

int main(void){
    for(int i=1;i<MAXN;++i)
        f[i]=f[i-1]+i;           //预处理第i行最少消耗的技能点数
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n-i+1;++j){
                int x;
                scanf("%d",&x);
                mp[i][j]=x+mp[i-1][j];
            }
        }
        memset(dp,0,sizeof(dp));
        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(j-1,0);p<n-i+1;++p){
                        dp[i][j][k]=max(dp[i][j][k],dp[i+1][p][k-j]+mp[j][i]);
                    }
                }
                ans=max(ans,dp[i][j][m]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}