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

#include <algorithm>
#include <iostream>
#include <vector>
long long INF = -1e18;
using namespace std;
//这道题相比普通version，就是加上了一个偏移量的约束，我们根据约束将不可达的元素值设为INF即可.

//建立s[i][j]记录每个元素的值，
//依旧采用动态规划，建立dp[i][j]，表示第i行第j列位置的最大数值之和的值。
//循环遍历确定最后一行每个元素是否可达，不可达赋值INF，可达赋予dp[i][j]对应s[i][j]值，
//然后从下往上确定各个dp[i][j]的值，max_value = max({dp[i+1][j], dp[i+1][j+1], dp[i+1][j+2]})，
//若dp[i][j]下方可达的三个元素值均为-INF，则dp[i][j]也赋值INF，记为不可达;否则dp[i][j] = max_value+s[i][j]
//由此不断向上，最后便能得到dp[0][0]
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<vector<long long>> s(n);
    for (int i = 0; i < n; i++) {
        s[i].resize(2*i + 1);
        for (int j = 0; j < 2 * i + 1; j++) {
            cin >> s[i][j]; // 得到s[i][j]的值
        }
    }
    // 题目指明k是作用在从第一行到最后一行的偏移量，因此我们只需研究最后一行的偏移量即可
    vector<vector<long long>> dp = s;
    for (int j = 0; j < 2 * n - 1; j++) {
        if (abs(j - (n-1)) > k) { // 第n-1列必为第n-1行的中心点，k是相对于中心点的偏移量
            dp[n-1][j] = INF;
        }
    }
    for (int i = n-2; i >= 0; i--) {
        for (int j = 0; j < 2 * i + 1; j++) {
            long long max_value = max({dp[i+1][j], dp[i+1][j+1], dp[i+1][j+2]});//大于两个元素取max，加{}
            // 注意下标索引，第i行第j列能达到第i+1行的第j，j+1，j+2列
            if (max_value > INF + 1) {
                dp[i][j] += max_value;
            }
            else {
                dp[i][j] = INF;
            }
        }
    }
    cout << dp[0][0];
}