首页 > ACM题库 > HDU-杭电 > hdu 2084 数塔-贪心-[解题报告]C++
2013
12-29

hdu 2084 数塔-贪心-[解题报告]C++

数塔

问题描述 :

在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的:

有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?

已经告诉你了,这是个DP的题目,你能AC吗?

输入:

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

输出:

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

样例输入:

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

样例输出:

30

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2084


简单的贪心思想:把最大的数添加进来s[i][j]+=max(s[i+1][j],s[i+1][j+1]);


#include<stdio.h>
#define max(a,b) (a)>(b)?(a):(b)
int s[100][100];
int main()
{
   int c,n,i,j,b;
   scanf("%d",&c);
   while(c--)
   {
     scanf("%d",&n);
     i=0;b=n;
     while(b--)
     {
       for(j=0;j<=i;j++)
          scanf("%d",&s[i][j]);  
       i++;
     }
     for(i=n-2;i>=0;i--)
         for(j=0;j<=i;j++)
            s[i][j]+=max(s[i+1][j],s[i+1][j+1]);
     printf("%d\n",s[0][0]);
   }
   return 0;
}

解题转自:http://blog.csdn.net/qinmusiyan/article/details/7982031


  1. [email protected]

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience