NYOJ-18-The Triangle

描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

输入
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

输出
Your program is to write to standard output. The highest sum is written as an integer.

样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出
30

逆向思维解题即可。

#include <stdio.h>
#define MAX(a, b) a > b ? a : b

int main(int argc, const char * argv[])
{
    int N;
    int num[5051], value[5051];

    while(~scanf("%d", &N))
    {
        int key = 1;
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                scanf("%d", num + key);
                value[key] = num[key];
                key++;
            }
        }

        for (int i = N - 1; i > 0; i--)
        {
            for (int j = i; j > 0; j--)
            {
                value[i * (i - 1) / 2 + j] += MAX(value[(1 + i) * i / 2 + j], value[(1 + i) * i / 2 + j + 1]);
            }
        }

        printf("%d\n", value[1]);
    }

    return 0;
}
全部评论

相关推荐

群星之怒:1.照片可以换更好一点的,可以适量P图,带一些发型,遮住额头,最好穿的正式一点,可以适当P图。2.内容太少。建议添加的:求职意向(随着投递岗位动态更改);项目经历(内容太少了建议添加一些说明,技术栈:用到了什么技术,还有你是怎么实现的,比如如何确保数据传输稳定的,角色注册用到了什么技术等等。)项目经历是大头,没有实习是硬伤,如果项目经理不突出的话基本很难过简历筛。3.有些内容不必要,比如自我评价,校内实践。如果实践和工作无关千万别写,不如多丰富丰富项目。4.排版建议:建议排版是先基础信息,然后教育背景(要突出和工作相关的课程),然后专业技能(一定要简短,不要长篇大论,写你会什么,会的程度就可以),然后是项目经历(一定要详细,占整个简历一定要超过一半,甚至超过百分之70都可以)。最后如果有一部分空白的话可以填补上校内获得的专业相关的奖项,没有就写点校园经历和自我评价。5.技术一定要够硬,禁得住拷打。还有作息尽量保证正常,不要太焦虑。我24双非本科还是非科班,秋招春招各找了一段实习结果都没有转正,当时都想噶了,最后6月份在校的尾巴也找到一份工作干到现在,找工作有时很看运气的不要急着自我否定。 加油
点赞 评论 收藏
分享
讯飞老萌新:站住!有人25还没有找到工作的吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务