天涯人论坛
先登录吧!!!
登录可以体验更多权限哦!!!
天涯人论坛

为编程爱好者打造一个学习、交流的平台。
 
首页首页  欢迎页欢迎页  注册注册  登录登录  
论坛刚刚起步,欢迎大家多多支持! 如果有想申请管理员或版主的请给管理员留言!!!
欢迎大家积极发帖!

分享 | 
 

 《数塔》

向下 
作者留言
让一切随风
Admin
avatar

帖子数 : 257
注册日期 : 12-11-03
年龄 : 26
地点 : 湖南

帖子主题: 《数塔》   周六 四月 20, 2013 8:47 pm

数塔
Problem Description 在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的:
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?

已经告诉你了,这是个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

代码:
#include <stdio.h>

int main(void)
{
    int    t[5600];
    int    n, i, j, c;

    scanf("%d",&c);
    while (c--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            for(j=0;j<=i;j++)
                scanf("%d",&t[(i+1)*(i+2)/2+j-1]);
        for(i=n-2;i>=0;i--)
            for(j=0;j<=i;j++)
                t[(i+1)*(i+2)/2+j-1]+=t[(i+3)*(i+2)/2+j-1]>t[(i+3)*(i+2)/2+j]?t[(i+3)*(i+2)/2+j-1]:t[(i+3)*(i+2)/2+j];
        printf("%d\n",t[0]);
    }
    return 0;
}
返回页首 向下
http://tyren.forumotion.com
 
《数塔》
返回页首 
1页/共1

您在这个论坛的权限:不能在这个论坛回复主题
天涯人论坛 :: 我爱编程 :: c语言-
转跳到: