注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 2048数塔  

2014-03-19 21:19:02|  分类: DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
//分析:此题采用动态规划从自底向上计算,如果我们要知道所走之和最大,那么最后一步肯定是走最后排数其中一个,向上退,倒数第二步肯定走最后排数对应的倒数第二排最大的一个(将最后对应最后步走的最大的数加起来存在倒数第二步的数组中:不理解的话先看思路在看程序),再向上推,一直推到最上面的第0步,那么a[0][0]最后所存的结果一定是最大的;

数塔

Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 5   Accepted Submission(s) : 4
Problem Description
在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少? [img]../data/images/2084-1.jpg[/img] 已经告诉你了,这是个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
30
 

Source
2006/1/15 ACM程序设计期末考试
#include<stdio.h>


int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,m,i,j;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
   int k[101][101];
   scanf("%d",&m);
   for(i=0;i<m;i++)
   {
    for(j=0;j<=i;j++)
    {
    scanf("%d",&k[i][j]);
   }
    }
    for(i=m-1;i>=0;i--)
    {
    for(j=0;j<i;j++)
    {
    k[i-1][j]=max(k[i][j]+k[i-1][j],k[i][j+1]+k[i-1][j]);
    }
   }
   printf("%d\n",k[0][0]);
}
}
return 0;
}
 
  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017