TOJ 4674 数塔II DP

心已赠人 2022-05-18 10:59 162阅读 0赞

## **4674: 数塔II** ##

**描述**

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少，并输出一条路径。  
7  
3 8  
8 1 0  
2 7 4 4  
4 5 2 6 5

**输入**

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间\[0,99\]内。

**输出**

对于每个测试实例，每行先输出可能得到的最大和，后面输出从第一层到最后一层所选数字的编号（即第几列的数）。

格式见样例。

**样例输入**

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

**样例输出**

30: 1 1 1 2 2

**提示**

从第一层到各层的数字分别为：  
第1层第1列：7  
第2层第1列：3  
第3层第1列：8  
第4层第2列：7  
第5层第2列：5

倒着做上去，用一个b数组记录一下初始值，再正着下来找值相等的。

#include<stdio.h>
    int main()
    {
    	int a[99][99],b[99][99];
    	int t,n,i,j,k;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);		
    		for(i=0;i<n;i++)
    		{
    			for(j=0;j<=i;j++)
    			{
    				scanf("%d",&a[i][j]);
    				b[i][j]=a[i][j];
    			}
    		}		 
    	    for(i=n-1;i>0;i--)
    	    {
        		for(j=0;j<i;j++)
        		{
    		    	if(a[i][j]>=a[i][j+1])
    	    		a[i-1][j]=a[i][j]+a[i-1][j];
    	    		else
    	    		a[i-1][j]=a[i][j+1]+a[i-1][j];
    		    }    		
        	}
        	printf("%d:",a[0][0]);
        	k=0;
        	for(i=0;i<n;i++)
    		{
    			printf(" %d",k+1);
    			for(j=0;j<=i+1;j++)
    			{
    				if(a[i][k]==a[i+1][j]+b[i][k]&&(j==k||j-1==k))
    				{
    					k=j;
    					break;
    				}
    			}
    		}
    		printf("\n");
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关 DP之数塔模型poj1157

题目：[poj1157LITTLE SHOP OF FLOWERS][poj1157_LITTLE SHOP OF FLOWERS] 题意：假设以最美观的方式布置花

水深无声/ 2022年08月27日 15:56/ 0 赞/ 153 阅读

相关 51nod 1002数塔取数 dp

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

不念不忘少年蓝@/ 2022年08月20日 13:11/ 0 赞/ 145 阅读

相关数塔——DP算法

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

古城微笑少年丶/ 2022年06月12日 01:41/ 0 赞/ 218 阅读

相关 hdu 2084 数塔（基础dp）

数塔Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

Bertha 。/ 2022年06月07日 05:46/ 0 赞/ 163 阅读

相关 HDU-2084-数塔（dp入门）

数塔 Problem Description 在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，

秒速五厘米/ 2022年05月27日 06:57/ 0 赞/ 185 阅读

相关 TOJ 4674 数塔II DP

4674: 数塔II 描述有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少，并输出一条路径。 7 3 8

心已赠人/ 2022年05月18日 10:59/ 0 赞/ 163 阅读

相关 TOJ 2865 Chopsticks DP

2865: Chopsticks 描述 In China, people use a pair of chopsticks to get food on the tab

拼搏现实的明天。/ 2022年05月17日 02:38/ 0 赞/ 98 阅读

相关 TOJ 1158 Computers DP

1158: Computers 描述 Everybody is fond of computers, but buying a new one is always a

た入场券/ 2022年05月17日 01:14/ 0 赞/ 189 阅读

相关 HDU2084 数塔 (dp算法）

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

深碍√TFBOYSˉ_/ 2022年05月08日 09:08/ 0 赞/ 184 阅读

相关 HDU2084：数塔(DP)

Problem Description 在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相

迈不过友情╰/ 2021年12月13日 23:34/ 0 赞/ 270 阅读