HDU 2084数塔

桃扇骨 2022-09-25 01:23 130阅读 0赞

A - 数塔

**Time Limit:**1000MS **Memory Limit:**32768KB **64bit IO Format:**%I64d & %I64u

Submit [Status][]

Description

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：  
  
有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？  
![79b65092734d6a263a9280f5b332c5b9][]  
已经告诉你了，这是个DP的题目，你能AC吗?

Input

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间\[0,99\]内。

Output

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

Sample Input

1
    5
    7
    3 8
    8 1 0 
    2 7 4 4
    4 5 2 6 5

Sample Output

AC 代码：

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    #define maxn 102
    int a[maxn][maxn];
    int i,j;
    void solve(int n)
    {
        for(i=n-1;i>=0;--i)
            for(j=0;j<=i;++j)
                a[i][j] = a[i][j] + max(a[i+1][j],a[i+1][j+1]);
    }
    int main()
    {
        int c, n;
        scanf("%d",&c);
        while(c--)
        {
            scanf("%d",&n);
            memset(a,0,sizeof(a));
            for(i=1;i<=n;i++)
                for(j=1;j<=i;j++)
                    scanf("%d",&a[i][j]);
            solve(n);
            printf("%d\n",a[0][0]);
        }
        return 0;
    }

[Status]: http://acm.hust.edu.cn/vjudge/contest/120638#status//A/0
[79b65092734d6a263a9280f5b332c5b9]: http://7xjob4.com1.z0.glb.clouddn.com/79b65092734d6a263a9280f5b332c5b9