dp入门（A）

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <string>
 5 #include <vector>
 6 
 7 using namespace std;
 8 typedef long long ll;
 9 
10 const int maxn = 1e6 +5;
11 
12 int dp[105][105];
13 
14 int main()
15 {
16     int t;
17     cin >> t;
18     while(t--)
19     {
20         memset(dp, 0, sizeof(dp));
21         int n ;
22         cin >> n;
23         for(int i = 1; i <= n; i++)
24         {
25             for(int j = 1; j <= i; j++)
26             {
27                 cin >> dp[i][j];
28             }
29         }
30         int Max = dp[1][1];
31         for(int i = 1; i <= n; i++)
32         {
33             for(int j = 1; j <= i; j++)
34             {
35                 dp[i][j] += max(dp[i-1][j], dp[i-1][j-1]);
36                 Max = max(Max, dp[i][j]);
37             }
38         }
39         cout << Max << endl;
40     }
41     return 0;
42 }