【每日一题】 Max Power

题意：
一个技能树一共有n行，第i行有n-i+1个技能，要学习第i行第j列技能的前提是学习第i-1行第j列和j+1列的技能，每个技能会带来一定收益。问给定技能的最多学习次数，能够得到的最大收益是多少。

思路：
dp。
将技能的收益按如下格式列出：
1 2 3 4 5
1 2 3 4
1 2 3
1 2
1
因为一个技能能够被学习的前提是其正上方技能和右上方技能被学习，而递推之后可以发现实际上是一个上三角区域内的技能全部被学习，所以可以推出要学习一个技能至少要用多少个技能点。
除此之外，不排除 第二列学习四个技能。第一列只学习了一个技能 的情况，所以不能仅根据行列来确定之前的技能的学习情况。
记：dp[i][j][k]第i列至最后一列中，第i列学习了j个技能，总共学习了k个技能时，带来的最大收益。
可以得到：dp[i][j][k]=max(dp[i][j][k],dp[i+1][l][k-j]+sum[j][i]);(j-1<=l<=n-i)
sum[j][i]表示第i列学习前j个技能能够得到的收益
l表示在第i+1列学习的技能数，因为要保证第i列第j个技能能学习，所以l>=j-1；l<=n-i则因为不能超过第i+1列的技能数。
而对于每次的k值，其应从j*(j+1)/2开始至m，因为其为最少需要学习的技能数。

最后从dp[1][j][m]中选出最大值即可。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=2e5+9;
const ll maxx=1e12+9;

int n,m,ar[55][55];
int sum[55][55],dp[55][55][1333];

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n-i+1;j++)
                scanf("%d",&ar[i][j]),sum[i][j]=sum[i-1][j]+ar[i][j];;
        memset(dp,0,sizeof dp);
        for(int i=n;i>=1;i--)
            for(int j=0;j<=n-i+1;j++)
                for(int k=j*(j+1)/2;k<=m;k++)
                    for(int l=j-1;l<=n-i;l++)
                        dp[i][j][k]=max(dp[i][j][k],dp[i+1][l][k-j]+sum[j][i]);
        int ans=0;
        for(int j=0;j<=n;j++) ans=max(ans,dp[1][j][m]);
        printf("%d\n",ans);
    }
}