题目描述

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

输入描述:

有多组样例输入，输入到文件结束.
每组样例第一行输入2个整数n(1<=n<=50)和m(1<=m<=1300)，对应题目上的含义。
接下来共有n行，第i行有n-i+1个数，代表这个技能学习后获得的战力加成(战力加成<=1000)。

输出描述:

输出最大的战力加成。

题解

首先，如果我们想要学习某个格子技能，这个格子的往上形成的倒三角必须全部学习

即在某一列我们都是连续的选择x个

我们设dp[i][j][k]为学习到第i列第j行的格子时我们已经学习了k个

那么转移方程为dp[i][j][k]=max(dp[i+1][p][k-j]+sum[j][i])

其中a[j][i]表示第i列前j个数的和

p要大于等于j-1，才能保证可以学习到第i列第j行的格子

所以枚举p，计算每个位置的dp[i][j][m]

答案即为dp[i][j][m]的最大值。

代码

/*
* Coder: niiii
* Language: cpp
*/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+100;
const int mod=1e9+7;

/*
dp[i][j][k]=dp[i-1][p][k-j]+sum[i][j]
p>=0&&p<=j+1
*/

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

int n,m,f[55];

int main(){
    while(cin>>n>>m){
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;++i){
            f[i]=f[i-1]+i;
            for(int j=1;j<=n-i+1;++j){
                cin>>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 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]+sum[j][i]);
                    }
                }
                ans=max(ans,dp[i][j][m]);
            }
        }
        cout<<ans<<endl;
    }
}