hdu 2084 数塔 (基础dp)
题意：dp入门题。。。数字三角形。。
思路：
昨天看mit公开课。。。讲到dp的精髓是sub-problem+ reuse…
为什么自底向上呢。。。
初始化dp[n][i] = a[n][i]其实是在处理只有最后一行的子问题。。。
需要特别强调的是。。处于某个子问题的时候。。。其他部分就好像不存在一样。。。
每一个点只能向下或者向右下两条路可走。。。
那么对于这一点的最大值。。。一定是取后来可走的两点的最大值加上自身。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月27日 星期三 12时56分28秒
4File Name :code/hdu/2084.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34int n;
35int a[N][N];
36int dp[N][N];
37int main()
38{
39 #ifndef ONLINE_JUDGE
40 freopen("code/in.txt","r",stdin);
41 #endif
42 int T;
43 cin>>T;
44 while (T--)
45 {
46 scanf("%d",&n);
47 ms(dp,0);
48 for ( int i = 1 ; i <= n ; i++)
49 for ( int j = 1 ; j <= i ; j++)
50 scanf("%d",&a[i][j]);
51
52 for ( int i = 1 ; i <= n ; i++)
53 dp[n][i] = a[n][i];
54
55 for ( int i = n-1 ; i >=1 ; i--)
56 for ( int j = 1 ; j <= i ; j++)
57 dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + a[i][j];
58
59 printf("%d\n",dp[1][1]);
60 }
61
62 #ifndef ONLINE_JUDGE
63 fclose(stdin);
64 #endif
65 return 0;
66}