若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1418: 1.5.1 Number Triangles 数字金字塔

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,128

题目描述

考虑在下面被显示的数字金字塔。写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。

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

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30

输入

第一个行包含 R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。

输出

单独的一行包含那个可能得到的最大的和。

样例输入

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

样例输出

30

参考代码

#include<stdio.h>
#include<string.h>
int max(int a,int b) 
{
    return a>b ? a:b;
}
int num[1000][1000],f[1000];
int main() 
{
    int R;
    int i,j;
    scanf("%d",&R);
    for (i=0;i<R;i++)
            for (j=0;j<i+1;j++)
                scanf("%d",&num[i][j]);
    for (i=0;i<R;i++)
            f[i]=num[R-1][i];
    for (i=R-1-1;i>=0;i--)
            for (j=0;j<=i;j++) 
    {
        f[j]=max(f[j],f[j+1])+num[i][j];
    }
    printf("%dn",f[0]);
return 0;
}

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Skip Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist