CUST-DP训练第一题-数塔问题

在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 

有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少? 
 
已经告诉你了,这是个DP的题目,你能AC吗?
Input输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间 0,990,99内。 
Output对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。 
Sample Input
1
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
Sample Output
30
在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?  已经告诉你了,这是个DP的题目,你能AC吗?
Input输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间0,990,99内。 Output对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。 Sample Input
1
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
Sample Output
30


对于这个题,我看了一下动态规划的一些基本概念,于是想出了个思路就是:建立另一个b数组,然后b数组对应位置存放的是从顶点走到这里,每条路径的最大和,a数组有多大,b数组就有多大,所以到b数组的最后一行,就是从顶点走到这个点的最大和,再从这几个点里找出更大的即可。


遇到的问题:

1.每一个不靠边的点,上面都会有两条路径,要找最大值。

2.多组数据要清空B数组!这也是我wa5次的原因...int b[N][N]={0};

具体代码如下:

#include<bits/stdc++.h>
#define N 100+10
using namespace std;
int main()
{

    int T,n,i,j;
    cin>>T;
    while(T--)
    {int a[N][N],b[N][N]={0};
        cin>>n;
        for(i=0;i<n;i++)
            for(j=0;j<=i;j++)
                cin>>a[i][j];
            b[0][0]=a[0][0];
        for(i=0;i<n;i++)
            for(j=0;j<=i;j++)
            {if(j-1<0)
                    b[i][j]=b[i-1][j]+a[i][j];
            else  if(b[i-1][j-1]+a[i][j]>=b[i][j])
                    b[i][j]=b[i-1][j-1]+a[i][j];
                  if(b[i-1][j]+a[i][j]>=b[i][j])
                    b[i][j]=b[i-1][j]+a[i][j];
            }
            int maxn=0;
            for(i=0;i<n;i++)
                if(b[n-1][i]>maxn)maxn=b[n-1][i];
            printf("%d\n",maxn);
    }
}


全部评论

相关推荐

序&nbsp;朋友们,好久不见。&nbsp;笔者在过去消失的五个月里被困在情绪牢笼中过的相当煎熬,一度丢失自己,觉得整个世界都是昏暗的。&nbsp;庆幸的是靠着自己纯硬扛也是走出来了。表达欲再度回归,所以真的很开心还有机会能在再和大家见面。&nbsp;破碎秋招&nbsp;抑郁情绪的引爆点必然是秋招期间遭受的打击了,从去年九月份腾讯转正被告知失败之后就开始疯狂投递简历,每天都在经历:简历挂、一面挂、二面挂、三面挂、HR面挂,每天睁开眼就被无所适从的挫败感包围。&nbsp;秋招的特点是即便流程走到最后一步也不一定会&nbsp;offer,因为还需要进入大池子进行横向对比,俗称泡池子,而这一泡我的大多数面试流程到后面就没了后文,这一度让我感觉非常绝望。我深知自己学历并...
SoNiC_X:我已经工作快2年了,当时高考没考好没去到想去的学校,觉得天要塌了;校招找不到工作,觉得天要塌了;现在工作觉得看不到未来,觉得天要塌了;最近最大的感悟就是:天会一直塌,但是生活也会一直继续下去,还是要调整好自己的心态,不要因为一时的困难把自己困住,要记住完蛋的日子永远在后头
点赞 评论 收藏
分享
04-03 11:37
武汉大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务