题意： 给定一个倒三角，共行，第行有个元素，选取必须先选取和，现在要求选择个元素，求选取的个元素可以获得的最大值。

题解：
学习参考了该篇题解：https://blog.nowcoder.net/n/4f95681bfb9e4bf29b49ce9aa321248d
由于选择一个元素，以其作为倒三角的顶点的三角形必须全部选中，所以从给定的倒三角的最右端开始，先处理第列，再处理第列，...，最后处理第列。

表示当前已经选择了这个元素，并且总共选择了个元素可以获得的最大值。
状态转移方程为
其中是该状态必选的。

状态转移的解释：由于这个状态必然选择了这个元素，

  • 对于第一维，由于第必然已经被选择了，所以该状态由后一列转移过来。
  • 对于第二维，第列的就必然被选择，因此的下限就是，上限就是第列的元素数即
  • 对于第三维，前一个状态相较于当前状态少了个元素，因此为

注意：
本题中有一个细节容易被忽略，即枚举行时应该从开始，因为要考虑到第行的元素转移过来是从后一列的第行转移过来的。
举个栗子：




，答案是选择
对于每一列保存表示该列元素均不被选择，那么就实现了跨列组合。

代码：

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

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f; 
}

const int N = 60, M = 1310;
int f[N][N][M];
int q[N][N];
int cnt[N];
int n, m;
int main()
{
    while(~scanf("%d%d", &n, &m)) {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n - i + 1; j++)
                q[i][j] = read(), q[i][j] += q[i - 1][j];

        m = min(m, n * (n + 1) / 2); //最多n * (n + 1) / 2个元素
        memset(f, 0, sizeof f);
        for(int i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + i;
        for(int j = n; j >= 1; j--)
            for(int i = 0; i <= n - j + 1; i++) //!!!!
                for(int k = cnt[i]; k <= m; k++)
                    for(int c = max(i - 1, 0); c <= n - j; c++) //第j+1列最多n-j个元素
                        f[j][i][k] = max(f[j][i][k], f[j + 1][c][k - i] + q[i][j]);

        int res = 0;
        for(int j = 1; j <= n; j++)
            for(int i = 1; i <= n - j + 1; i++)
                res = max(res, f[j][i][m]);

        printf("%d\n", res);
    }    
    return 0;
}