HDOJ 2084 数塔【dp】

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2084

状态是从当前位置出发的最大和
转移方程是当前的数值加上下面两个方向的位置开始的最大和
即dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 #define clr(c) memset(c, 0, sizeof(c));
 7 const int MAXL = 105;
 8 int C, N;
 9 int a[MAXL][MAXL];
10 int dp[MAXL][MAXL];
11 
12 void Resolve(){
13     clr(dp);
14     for(int j = 1; j <= N; j++) dp[N][j] = a[N][j];
15     for(int i = N-1; i >= 1; i--){
16         for(int j = 1; j <= i; j++){
17             dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
18         }
19     }
20 //    for(int i = 1; i <= N; i++){
21 //        for(int j = 1; j <= i; j++){
22 //            printf("%d  ", dp[i][j]);
23 //        }
24 //        printf("
");
25 //    }
26 }
27 
28 int main(){
29     clr(a);
30     scanf("%d", &C);
31     while(C--){
32         scanf("%d", &N);
33         for(int i = 1; i <= N; i++){
34             for(int j = 1; j <= i; j++){
35                 scanf("%d", &a[i][j]);
36             }
37         }
38         Resolve();
39         printf("%d
", dp[1][1]);
40     }
41 
42     return 0;
43 }

HDOJ 2084 数塔 【dp】

HDOJ 2084 数塔 【dp】

HDOJ 2084 数塔【dp】

HDOJ 2084 数塔【dp】