hdu 2084 数塔

最基本的DP问题了~
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <string>
 5 #include <algorithm>
 6 using namespace std;
 7 int C, n;
 8 int dp[110][110];
 9 int a[110][100];
10 int main(){
11     scanf("%d", &C);
12     while(C--){
13         scanf("%d",&n);
14         for(int i = 1; i <= n; i++){
15             for(int j = 1; j <= i; j++) scanf("%d", &a[i][j]);
16         }
17         memset(dp, 0, sizeof(dp));
18         for(int i = 1; i <= n; i++) dp[n][i] = a[n][i];
19         for(int i = n-1; i >= 1; i--){
20             for(int j = 1; j <= i; j++){
21                 dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
22             }
23         }
24         printf("%d
", dp[1][1]);
25     }
26     
27     return 0;
28 }