HDU

题意：

找出一套从底到顶的一条线，使得加和最大

思路：

是一道明显的动态规划问题，如图解释

我们只需要一行一行进行比较，每次选取较大的即可

代码：

#include<iostream>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

const int maxn = 110;
int mp[maxn][maxn];
int dp[maxn][maxn];

int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        memset(dp, 0, sizeof(dp));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                scanf("%d", &mp[i][j]);
            }
        }
        for (int i = n; i >= 1; i--) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = mp[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
            }
        }
        printf("%d
", dp[1][1]);
    }
    return 0;
}