```   1 #include <iostream>
2 using namespace std;
3 const int N=110;
4 int a[N][N];
5 int f[N][N];
6 int n;
7 void Init()
8 {
9         scanf("%d",&n);
10         for(int i=0;i<n;i++)
11                 for(int j=0;j<=i;j++)
12                         scanf("%d",&a[i][j]);
13         memset(f,-1,sizeof(f));
14 }
15 int DP(int i,int j)
16 {
17         int ans;
18         if(f[i][j]>=0)
19                         return f[i][j];
20         if(i==n-1)
21                 ans=a[i][j];
22         else
23         {
24                 if(DP(i+1,j)>DP(i+1,j+1))
25                         ans=a[i][j]+DP(i+1,j);
26                 else
27                         ans=a[i][j]+DP(i+1,j+1);
28         }
29         f[i][j]=ans;
30         return f[i][j];
31 }
32 int main()
33 {
34         int test;
35         cin>>test;
36         while(test-->0)
37         {
38                 Init();
39                 printf("%d\n",DP(0,0));
40         }
41 }
```

```   1 //非递规 dp  written by czy
2 #include <stdio.h>
3 #include <memory.h>
4
5 int tower[102][102];
6 int tmax[102][102];
7
8 int max(int &a, int &b){
9     return a>b?a:b;
10 }
11
12 int main(){
13     int Case;
14     scanf("%d",&Case);
15         while(Case--){
16             int tHeight;
17             scanf("%d", &tHeight);
18             for(int i = 1; i <= tHeight; i++){
19                 for(int j = 1; j <= i; j++){
20                     scanf("%d", &tower[i][j]);
21                 }
22             }
23             memset(tmax,0,101*101*4);
24
25             //dp
26             for(int k = tHeight; k > 0; k--){
27                 for(int l = 1; l <= k; l++)
28                     if(k==tHeight)
29                         tmax[k][l] = tower[k][l];
30                     else
31                         tmax[k][l] = tower[k][l] + max(tmax[k+1][l],tmax[k+1][l+1]);
32             }
33             printf("%d\n", tmax[1][1]);
34         }
35
36
37     return 0;
38 }
```

hdu2084 参考答案 (last edited 2008-11-05 14:50:02 by 218)

ch3n2k.com | Copyright (c) 2004-2022 czk.