从下网上推。
#include<cstdio> #include<cstring> #include<vector> #include<iostream> #include<algorithm> using namespace std; int a[400][400]; int dp[400][400]; int main() { int n; while(scanf("%d",&n)!=EOF) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { scanf("%d",&a[i][j]); if(i==n) dp[i][j]=a[i][j]; } } for(int i=n-1;i>=1;i--) { for(int j=1;j<=i;j++) { dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]; } } printf("%d\n",dp[1][1]); } return 0; }