三角形取数(Hard Version)

思路

拿到题先理解这个"三角形"的结构：第 行有 个数，视觉上就是一个正三角形，每往下一行两边各多一个数。

从顶点出发，每一步可以往左下、正下、右下三个方向走。记左下走了 次、右下走了 次，要求最终 ，问路径上数字之和的最大值。

关键观察： 每一步的列变化量分别是 （左下不变列号，但因为下一行比当前行左边多了一个位置，相当于相对位移 ）、（正下）、（右下）。起始在第 行正中央，设"偏移量"为 ，那么到第 行时，列号 。

约束 就等价于最终列号满足 ，即 。

这个观察把问题彻底简化了——约束只作用在最后一行的列号范围上，中间过程完全不需要额外状态。

所以就是一个最普通的三角形 DP：

$$

其中 对应从上一行的"左下"走过来（列号不变）， 是"正下"， 是"右下"。

最后答案就是 。

用滚动数组优化掉行的维度，空间 。

注意点：

  • 数值范围 ，路径长度最大 ，总和可能到 ，要用 long long。
  • 初始化为极小值，只有起点 是有效状态。

代码

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    const long long NEG_INF = -4e18;
    int maxcol = 2 * n;
    vector<long long> dp(maxcol, NEG_INF);

    long long val;
    cin >> val;
    dp[1] = val; // 第1行唯一的数，列号1

    for(int i = 2; i <= n; i++){
        int cols = 2 * i - 1;
        int prevCols = 2 * (i - 1) - 1;
        vector<long long> a(cols + 1);
        for(int j = 1; j <= cols; j++) cin >> a[j];

        vector<long long> ndp(maxcol, NEG_INF);
        for(int pj = 1; pj <= prevCols; pj++){
            if(dp[pj] == NEG_INF) continue;
            // 左下：列号不变
            if(pj <= cols)
                ndp[pj] = max(ndp[pj], dp[pj] + a[pj]);
            // 正下：列号+1
            if(pj + 1 <= cols)
                ndp[pj+1] = max(ndp[pj+1], dp[pj] + a[pj+1]);
            // 右下：列号+2
            if(pj + 2 <= cols)
                ndp[pj+2] = max(ndp[pj+2], dp[pj] + a[pj+2]);
        }
        dp = ndp;
    }

    long long ans = NEG_INF;
    for(int j = max(1, n - k); j <= min(2*n - 1, n + k); j++){
        ans = max(ans, dp[j]);
    }
    cout << ans << "\n";
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        final long NEG_INF = (long)(-4e18);
        int maxcol = 2 * n;
        long[] dp = new long[maxcol];
        Arrays.fill(dp, NEG_INF);

        st = new StringTokenizer(br.readLine());
        dp[1] = Long.parseLong(st.nextToken());

        for (int i = 2; i <= n; i++) {
            int cols = 2 * i - 1;
            int prevCols = 2 * (i - 1) - 1;
            long[] a = new long[cols + 1];
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= cols; j++)
                a[j] = Long.parseLong(st.nextToken());

            long[] ndp = new long[maxcol];
            Arrays.fill(ndp, NEG_INF);

            for (int pj = 1; pj <= prevCols; pj++) {
                if (dp[pj] == NEG_INF) continue;
                if (pj <= cols)
                    ndp[pj] = Math.max(ndp[pj], dp[pj] + a[pj]);
                if (pj + 1 <= cols)
                    ndp[pj+1] = Math.max(ndp[pj+1], dp[pj] + a[pj+1]);
                if (pj + 2 <= cols)
                    ndp[pj+2] = Math.max(ndp[pj+2], dp[pj] + a[pj+2]);
            }
            dp = ndp;
        }

        long ans = NEG_INF;
        for (int j = Math.max(1, n - k); j <= Math.min(2*n - 1, n + k); j++)
            ans = Math.max(ans, dp[j]);
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    NEG_INF = float('-inf')
    maxcol = 2 * n
    dp = [NEG_INF] * maxcol

    val = int(input().split()[0])
    dp[1] = val

    for i in range(2, n + 1):
        cols = 2 * i - 1
        prev_cols = 2 * (i - 1) - 1
        a = [0] + list(map(int, input().split()))

        ndp = [NEG_INF] * maxcol
        for pj in range(1, prev_cols + 1):
            if dp[pj] == NEG_INF:
                continue
            if pj <= cols:
                v = dp[pj] + a[pj]
                if v > ndp[pj]:
                    ndp[pj] = v
            if pj + 1 <= cols:
                v = dp[pj] + a[pj + 1]
                if v > ndp[pj + 1]:
                    ndp[pj + 1] = v
            if pj + 2 <= cols:
                v = dp[pj] + a[pj + 2]
                if v > ndp[pj + 2]:
                    ndp[pj + 2] = v
        dp = ndp

    ans = NEG_INF
    lo = max(1, n - k)
    hi = min(2 * n - 1, n + k)
    for j in range(lo, hi + 1):
        if dp[j] > ans:
            ans = dp[j]
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l));
rl.on('close', () => {
    const [n, k] = lines[0].split(' ').map(Number);
    const NEG_INF = -4e18;
    const maxcol = 2 * n;
    let dp = new Array(maxcol).fill(NEG_INF);

    dp[1] = parseInt(lines[1]);

    for (let i = 2; i <= n; i++) {
        const cols = 2 * i - 1;
        const prevCols = 2 * (i - 1) - 1;
        const parts = lines[i].split(' ').map(Number);
        const a = [0, ...parts];

        const ndp = new Array(maxcol).fill(NEG_INF);
        for (let pj = 1; pj <= prevCols; pj++) {
            if (dp[pj] === NEG_INF) continue;
            if (pj <= cols)
                ndp[pj] = Math.max(ndp[pj], dp[pj] + a[pj]);
            if (pj + 1 <= cols)
                ndp[pj+1] = Math.max(ndp[pj+1], dp[pj] + a[pj+1]);
            if (pj + 2 <= cols)
                ndp[pj+2] = Math.max(ndp[pj+2], dp[pj] + a[pj+2]);
        }
        dp = ndp;
    }

    let ans = NEG_INF;
    for (let j = Math.max(1, n - k); j <= Math.min(2*n - 1, n + k); j++) {
        ans = Math.max(ans, dp[j]);
    }
    console.log(ans);
});

复杂度分析

  • 时间复杂度: 。每行最多 个元素，遍历 行，总操作量 。
  • 空间复杂度: 。滚动数组只保留一行的 DP 值。

小结

这道题看着是三角形路径求最大和的"进阶版"——多了左右移动次数差的限制。但仔细分析就会发现，起始位置固定在正中央，每走一步左下/右下分别会让"偏移量"减一/加一，而直走不变偏移。到最后一行时偏移量就等于 ，直接反映在列号上。所以 这个约束根本不需要额外维度来追踪，只需要在最后一行限制取答案的列号范围即可。整道题本质上就是一个标准的三角形 DP， 轻松搞定。