题解 | 三角形取数(Hard Version)

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author supermejane
 * @date 2025/10/9 12:00
 * @description BGN69 三角形取数(Hard Version)
 */
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int size = 2 * n - 1;
        int[][] a = new int[n][size];
	  	//dp[][] Long精度
        long[][] dp =  new long[n][size];
        a[0][n - 1] = in.nextInt();
	  
	  	//初始化dp[][]
        Arrays.stream(dp).forEach(e -> Arrays.fill(e, Long.MIN_VALUE));
        dp[0][n - 1] = a[0][n - 1];


        long minVal = Long.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            for (int j = n - 1 - i; j <= n - 1 + i; j++) {
                a[i][j] = in.nextInt();
			  	//仅仅防止越界，不用额外处理i >= n - i && i <= n - 2 + i的边界
                 dp[i][j] = Math.max(Math.max(j - 1 >= 0 ? dp[i - 1][j - 1] : minVal, j + 1 <= size - 1 ? dp[i - 1][j + 1] : minVal), dp[i - 1][j]) + a[i][j];
            }
        }

        long result = minVal;
	  	//处理k的限制
        for (int i = Math.max(n - 1 - k, 0); i <= Math.min(n - 1 + k, size - 1); i++) {
            result = Math.max(result, dp[n - 1][i]);
        }
        System.out.println(result);
    }
}