[TYVJ] P1044 数字三角形

数字三角形

背景 Background

09年 USACO 11月月赛  铜牌第一道

 

描述 Description

示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径，使该路径所经过的数字的总和最大。
　　每一步可沿左斜线向下或右斜线向下走；
　　1<三角形行数<25；
　　三角形中的数字为整数<1000；

 

输入格式 InputFormat

第一行为N，表示有N行
后面N行表示三角形每条路的路径权

 

输出格式 OutputFormat

路径所经过的数字的总和最大的答案

 

样例输入 SampleInput [复制数据]

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

样例输出 SampleOutput [复制数据]

30

数据范围和注释 Hint

搜索80分，记忆化搜索AC

 

题解：简单的动态规划

 

代码：

#include<stdio.h>
int 
max(int a,int b)
{ 
    if (a>b) return(a);
    else return(b);
}

int 
main(void)
{
    int i,j,n,x,a[50][50];
    
    scanf("%d
",&n);
    for (i=1;i<=n;i++)
        for (j=1;j<=i;j++)
        {
            scanf("%d",&a[i][j]);
            a[i][j]+=max(a[i-1][j-1],a[i-1][j]);
        }
    x=-351111;
    for (i=1;i<=n;i++)
    x=max(x,a[n][i]);
    
    printf("%d
",x);
    return 0;
}