#include<bits/stdc++.h> using namespace std; int a[1001][1001]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>a[i][j]; int maxx=0; for(int i=2;i<=n;i++){ for(int j=1;j<=i;j++){ a[i][j]+=max(a[i-1][j],a[i-1][j-1]); maxx=max(maxx,a[i][j]); } } cout<<maxx; return 0; }

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

#include<iostream> using namespace std; int a[1005][1995]; int main() { int n; cin >> n; for (int i=1; i<=n; i++) { for (int j=1; j<=i; j++){ cin >> a[i][j]; } } //i = n-1 从倒数第二行 for (int i=n-1; i>=1; i--){ // for(int j=1; j<=i; j++) { a[i][j] = a[i][j] + max(a[i+1][j],a[i+1][j+1]); } } cout << a[1][1]; return 0; }

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