每日一题 7月29日Max Power DP

链接：https://ac.nowcoder.com/acm/problem/20663
来源：牛客网

题目描述

小卤蛋刚把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)。

输出描述:

输出最大的战力加成。

输入

4 3
1 4 1 9
2 3 5
6 1
66

输出

15

思路

对于一个技能塔

学习红色的技能时，必须把倒三角全部学习完。 表示i-n行的所有行学习了k个技能，并且第i行学习了j个技能的最大战力加成。

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

int a[55][55], s[55][55], f[55][55][1305];
int main() {

    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        memset(s, 0, sizeof(s));
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n-i+1; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        for(int j=1; j<=n; j++) {
            for(int i=1; i<=n-j+1; i++) {
                s[j][i]=s[j][i-1]+a[i][j];
            }
        }


        memset(f, 0xc0, sizeof(f));
        int mx=0;
        f[n+1][0][0]=0;
        for(int i=n; i>=1; i--) {
            for(int j=0; j<=n-i+1; j++) {
                for(int k=j; k<=m; k++) {
                    for(int p=max(j-1, 0); p<=n-i; p++) {
                        f[i][j][k]=max(f[i][j][k], f[i+1][p][k-j]+s[i][j]);
                        //cout<<i<<" "<<j<<" "<<k<<" "<<f[i][j][k]<<endl;
                    }
                }
                mx=max(mx, f[i][j][m]);
            }
        }
        printf("%d\n", mx);
    }



    return 0;

}