题解

#include<iostream>
using namespace std;
int main(){
    int r;
    cin>>r;
    int s[r][r]={},mx[r][r]={};
    for(int i=0;i<r;i++)for(int j=0;j<=i;j++)cin>>s[i][j];
    mx[0][0]=s[0][0];
    for(int i=1;i<r;i++)mx[i][0]=s[i][0]+mx[i-1][0];
    for(int i=1;i<r;i++)for(int j=1;j<=i;j++){
        mx[i][j]=max(mx[i-1][j],mx[i-1][j-1])+s[i][j];
    }int maxn=0;
    for(int i=0;i<r;i++)maxn=max(maxn,mx[r-1][i]);
    cout<<maxn<<endl;
    return 0;
}

这是一道经典动态规划题，可以发现，贪心是取不到最大值，因此可以套用公式mx[i][j]=max(mx[i-1][j],mx[i-1][j-1])+s[i][j]来递推