Max Power

题意：
有一颗n层的技能树，第i层有n-i+1个技能,学习第i层第j个技能则必须先学习第i-1层第i和i+1个技能，第一层的技能可以直接学。你能学m个技能，求你最大的战力加成为多少？

思路：
dp
我们发现如果第i层第j个技能学习了，则以它为底的倒三角的技能一定学习了。
设dp[i][j][r]为第n列到第i列中学习了r个技能且第i列学习了前j个技能时的最大加成。
sum[i][j]为第j列前i行的和。
我们可以写出状态方程：
dp[i][j][r]=max(dp[i+1][p][r-j]+sum[j][i])(p>=j-1(满足学习前置技能条件))

代码：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll inf=1000000007;

int dp[55][55][1350], a[55][55], sum[55][55];

int main()
{
    int n, m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n-i+1;j++)
            {
                scanf("%d",&a[i][j]);
                sum[i][j]=sum[i-1][j]+a[i][j];
            }
        }
        int ans=0;
        for(int i=n;i>=1;i--)
        {
            for(int j=0;j<=n-i+1;j++)
            {
                for(int r=j*(j+1)/2;r<=m;r++)
                {
                    for(int l=max(0,j-1);l<=n-i;l++)
                    {
                        dp[i][j][r]=max(dp[i][j][r],dp[i+1][l][r-j]+sum[j][i]);
                        if(r==m)
                        {
                            ans=max(ans,dp[i][j][r]);
                        }
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}