hdu2084 DP

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 int maxx(int a,int b)
 6 {
 7     if(a>b)return a;
 8     return b;
 9 }
10 
11 int main()
12 {
13     int a[105][105];
14     int c,N,dp[105][105],max;
15     while(cin>>c)
16     {
17         while(c--)
18         {
19             memset(dp,0,sizeof(dp));
20             memset(a,0,sizeof(a));
21             cin>>N;
22             for(int i=0;i<N;i++)
23                 for(int j=0;j<=i;j++)
24                 {
25                     cin>>a[i][j];
26                 }
27             dp[0][0]=a[0][0];
28             max=a[0][0];//刚开始没有这句，wa了
29             for(int i=1;i<N;i++)
30             for(int j=0;j<=i;j++)
31             {
32                 if(j==0)
33                 dp[i][j]=dp[i-1][j]+a[i][j];
34                 else if(j==i)
35                 dp[i][j]=dp[i-1][j-1]+a[i][j];
36                 else dp[i][j]=maxx(dp[i-1][j-1],dp[i-1][j])+a[i][j]; 
37             }
38             for(int i=0;i<N;i++)
39             {
40                 if(dp[N-1][i]>max)
41                 max=dp[N-1][i];    
42             }
43             cout<<max<<endl;
44         }
45     }
46     return 0;
47  }