带路径的数塔 #include " iostream " using namespace std; int main(){ int a[ 100 ][ 100 ],b[ 100 ]; int i,j; int n; while (cin >> n) { for (i = 0 ;i < n;i ++ ) for (j = 0 ;j <= i;j ++ ) cin >> a[i][j]; int t = 0 ; int y = a[ 0 ][ 0 ]; for (i = n - 2 ;i >= 0 ;i -- ) { int max = 0 ,k = 0 ; for (j = 0 ;j <= i;j ++ ) { if (a[i + 1 ][j] > a[i + 1 ][j + 1 ])//将每次出现的最大路径保存即可 { a[i][j] += a[i + 1 ][j]; if (max < a[i][j]) { max = a[i][j]; k = a[i + 1 ][j]; b[t ++ ] = k;} } else { a[i][j] += a[i + 1 ][j + 1 ]; if (max < a[i][j]) {max = a[i][j]; k = a[i + 1 ][j + 1 ]; b[t ++ ] = k;} } } } cout << a[ 0 ][ 0 ] << endl; cout << y << " " ; if (n % 2 == 0 ) { for (i = t - 1 ;i >= 0 ;i -- ) //求路径之差 { cout << b[i] - b[i - 1 ]; if (i != 0 ) cout << " " ; } } else { for (i = t - 1 ;i >= 2 ;i -- ) { cout << b[i] - b[i - 1 ]; if (i != 2 ) cout << " " ; } cout << " " << b[ 0 ]; } // cout<<endl; } return 0 ;} 1 #include " iostream " 2 #define M 100 3 using namespace std; 4 int Max( int a, int b) 5 { 6 return a > b ? a:b; 7 } 8 int main() 9 { 10 int m,n; 11 int i,j; 12 int dp[M][M]; 13 cin >> m; 14 while (m -- ) 15 { 16 cin >> n; 17 18 for (i = 0 ;i < n;i ++ ) 19 for (j = 0 ;j <= i;j ++ ) 20 cin >> dp[i][j]; 21 22 for (i = n - 2 ;i >= 0 ;i -- ) 23 { 24 for (j = 0 ;j < n;j ++ ) 25 dp[i][j] += Max(dp[i + 1 ][j],dp[i + 1 ][j + 1 ]); 26 } 27 cout << dp[ 0 ][ 0 ] << endl; 28 } 29 return 0 ; 30 }