AcWing_898 数字三角形(线性DP)

13 Mar 2024 703字 3分

AcWing

898. 数字三角形

f[i][j]: 从根节点到第i层，第j列那个点的最大的价值和。

状态转移方程：f[i][j] = max{f[i-1][j-1], f[i-1][j]} + w[i][j].

初始化：令f[i][j]全部为-INF，这样状态的转移只能由有值的节点向下转移，排除掉了所有越界点。令f[0][0] = 0，方便转移出f[1][1](也可令f[1][1] = w[1][1]).

#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 510, INF = 0x3f3f3f3f;
int w[N][N], f[N][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) f[i][j] = -INF;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++) cin >> w[i][j];
    }
    f[0][0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + w[i][j];
        }
    }
    int maxele = -INF;
    for(int i = 1; i <= n; i++) if(f[n][i] > maxele) maxele = f[n][i];
    cout << maxele << endl;
    return 0;
}