题目大意

给一个 层的三角形，第 层有 个元素。设第 行第 列的元素为 。一开始只有第一层的元素可选择，其他层的元素 可被选择当且仅当 和 均被选择。求共选择 个元素的元素和最大值。

题解

DP。设 表示后 列用完，选了 个元素，且第 列共选择了前 行元素的最大和。那么有

其中 表示第 列前 行元素的和。
朴素转移的时间复杂度为 ，可以通过维护 ，即后缀最大值进行优化，优化后的时间复杂度为 。

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, a[55][55], sum[55][55] = {0}, sum2[55][55];
int f[55][1305][55], tri[55];
int g[55][1305][55];
/* inline int q(int x, int y, int bc){
    int rbc = 
    return sum2[y][y + bc]
}*/
void init(){
    REP(i, 1, n)
        REP(j, 1, n - i + 1)
            a[i][j] = read();
    REP(i, 1, n){
        REP(j, 1, n - i + 1)
            sum[j][i] = sum[j - 1][i] + a[j][i];
    }
    REPR(i, n, 1){
        sum2[i][i] = a[1][i];
        REPR(j, i - 1, 1)
            sum2[j][i] = sum2[j + 1][i] + sum[i - j + 1][j];
    }
    /* REP(i, 1, n)
        REP(j, 1, n - i + 1)
            sum[j][i] += sum[j][i - 1]; 
    tri[0] = 0;
    REP(i, 1, n)
        tri[i] = tri[i - 1] + i; */
}
void solve(){
    memset(f, 0xC0, sizeof(f));
    memset(g, 0xC0, sizeof(g));
    f[n + 1][0][0] = g[n + 1][0][0] = 0;
    REPR(i, n, 1){
        REPR(j, n - i + 1, 1){
            int dd = sum[j][i];
            REP(t, j, m){
                f[i][t][j] = g[i + 1][t - j][j - 1] + dd,
                g[i][t][j] = max(f[i][t][j], g[i][t][j + 1]);
            }
        }
        REP(t, 0, m){
            f[i][t][0] = g[i + 1][t][0],
            g[i][t][0] = max(f[i][t][0], g[i][t][1]);
        }
    }
    int ans = 0;
    REP(i, 0, n)
        ans = max(ans, f[1][m][i]);
    printf("%d\n", ans);
}
int main(){
    while (scanf("%d%d", &n, &m) == 2){
        init();
        solve();
    }
    return 0;
}