文字教学

这是一道动态规划问题，核心是记录路径和乘3次数的状态，避免重复计算。

1. 状态定义：用 prev[j][t] 表示走到上一行第 j 个位置，用了 t 次乘3时的最大得分；curr[j][t] 表示当前行的状态。
2. 状态转移：对于当前位置，有两种选择：
   • 不乘3：从上一行的左上方或正上方转移，乘3次数不变。
   • 乘3（次数未超k）：从上一行转移，乘3次数加1，当前数字乘3。
3. 滚动数组优化：因为当前行只和上一行有关，用两个二维数组交替更新，节省空间。

代码

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

typedef long long ll;
const ll INF = 1e18;

ll a[105][105];
ll pre[105][5055];
ll cur[105][5055];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            cin >> a[i][j];
        }
    }

    for (int j = 0; j <= 100; ++j) {
        for (int t = 0; t <= 5050; ++t) {
            pre[j][t] = -INF;
        }
    }
    pre[1][0] = a[1][1];
    if (k >= 1) pre[1][1] = a[1][1] * 3;

    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j <= 100; ++j) {
            for (int t = 0; t <= 5050; ++t) {
                cur[j][t] = -INF;
            }
        }
        for (int j = 1; j <= i; ++j) {
            for (int t = 0; t <= k; ++t) {
                ll v1 = -INF;
                if (j > 1) v1 = max(v1, pre[j-1][t]);
                if (j < i) v1 = max(v1, pre[j][t]);
                if (v1 != -INF) v1 += a[i][j];

                ll v2 = -INF;
                if (t >= 1) {
                    if (j > 1) v2 = max(v2, pre[j-1][t-1]);
                    if (j < i) v2 = max(v2, pre[j][t-1]);
                    if (v2 != -INF) v2 += a[i][j] * 3;
                }

                cur[j][t] = max(v1, v2);
            }
        }
        for (int j = 1; j <= i; ++j) {
            for (int t = 0; t <= k; ++t) {
                pre[j][t] = cur[j][t];
            }
        }
    }

    ll ans = -INF;
    for (int j = 1; j <= n; ++j) {
        for (int t = 0; t <= k; ++t) {
            ans = max(ans, pre[j][t]);
        }
    }
    cout << ans << endl;
    return 0;
}