求助

Xsj20130318 @ 2024-07-25 10:50:43

by yanhaoming @ 2024-07-27 12:03:01

这题我是用动态规划实现的。

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 

把最后一行存储结果，状态转移方程：
ms[j] = max(ms[j],ms[j+1])+d[i][j （从底向上求） 最后上代码：

# include<bits/stdc++.h>
using namespace std;
int d[1010][1010];
int* ms;
int n;
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j<=i;j++){
            cin >> d[i][j];
        }
    }
    ms = d[n];
    for(int i = n-1;i>0;i--){
        for(int j = 1;j<=n;j++){
            ms[j] = max(ms[j],ms[j+1])+d[i][j];
        }
    }
    cout << ms[1];
}