数塔

朴灿烈づ我的快乐病毒、 2022-04-24 11:34 307阅读 0赞

给定一个数塔，如下图所示。在此数塔中，从顶部出发，在每一节点可以选择走左下或右下，一直走到底层。请找出一条路径，使路径上的数值和最大。

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>9</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>12</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>15</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>10</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>6</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>8</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>2</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>18</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>9</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>5</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;"> <p>19</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>7</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>10</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>4</p> </td> 
   <td style="vertical-align:top;">&nbsp;</td> 
   <td style="vertical-align:top;"> <p>16</p> </td> 
  </tr> 
 </tbody> 
</table>

【输入形式】

输入时第一行一个整数n，表示该数塔的行数，其余n行表示该塔每行的数值

【输出形式】

输出包含两行，第一行为最大路径上的数值之和， 第二行n个数字为从上而下最大路径数值

【样例输入】

5
    9
    12 15
    10 6 8
    2 18 9 5
    19 7 10 4 16

【样例输出】

59
    9 12 10 18 10

ac代码：

\#include<iostream>  
using namespace std;  
int main() \{  
    int n,i,j,k=0;  
    int max(int,int);  
    cin>>n;  
    int z\[n\]\[n\],x\[n\]\[n\],t\[n\]=\{0\};  
    for(i=0; i<n; i++) \{  
        for(j=0; j<=i; j++) \{  
            cin>>z\[i\]\[j\];  
        \}  
    \}  
    for(i=0;i<n;i++)\{  
        x\[n-1\]\[i\]=z\[n-1\]\[i\];  
    \}  
    for(i=n-1;i>0;i--)\{  
        for(j=0;j<=i-1;j++)\{  
            x\[i-1\]\[j\]=max(x\[i\]\[j\],x\[i\]\[j+1\])+z\[i-1\]\[j\];  
        \}  
    \}  
    t\[0\]=x\[0\]\[0\];  
    for(i=1;i<n;i++)\{  
        if(x\[i\]\[k\]>x\[i\]\[k+1\])\{  
            t\[i\]=x\[i\]\[k\];  
        \}  
        else\{  
            t\[i\]=x\[i\]\[k+1\];  
            k++;  
        \}  
    \}  
    cout<<t\[0\]<<endl;  
    for(i=0;i<n;i++)\{  
        for(j=0;j<=i;j++)\{  
            if(t\[i\]==x\[i\]\[j\])\{  
                cout<<z\[i\]\[j\]<<' ';  
                break;  
            \}  
        \}  
    \}  
\}  
int max(int a,int b)\{  
        if(a>b) return a;  
        else return b;  
    \}

发表评论取消回复

表情：

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

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

相关阅读

相关数塔问题

问题描述： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nL

我会带着你远行/ 2023年07月19日 05:55/ 0 赞/ 12 阅读

相关 HDU【数塔】

include<iostream> include<algorithm> using namespace std; define MAX 101

今天药忘吃喽~/ 2022年11月19日 01:11/ 0 赞/ 148 阅读

相关 HDU 2084数塔

A - 数塔 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit [St

桃扇骨/ 2022年09月25日 01:23/ 0 赞/ 130 阅读

相关动态规划：数塔问题

动态规划问题我训练过一些题目，但是感觉自己掌握的还不是特别好！下面以一道经典的动态规划题目说明动态规划算法的思想，文末会官方的给出对动态规划的文字叙述。先看题目：如下

本是古典何须时尚/ 2022年08月08日 12:49/ 0 赞/ 173 阅读

相关 hdu2084——数塔

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=2084][http_acm.hdu.edu.cn_showproblem.p

以你之姓@/ 2022年07月16日 07:57/ 0 赞/ 132 阅读

相关数塔——DP算法

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

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

相关问题 A: 数塔

一：题目描述给定一个数塔，如下图所示。在此数塔中，从顶部出发，在每一节点可以选择走左下或右下，一直走到底层。请找出一条路径，使路径上的数值和最大。 9 12 15

迷南。/ 2022年06月10日 00:55/ 0 赞/ 144 阅读

相关数塔问题

[数塔][Link 1] Description 在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层

系统管理员/ 2022年06月01日 02:40/ 0 赞/ 213 阅读

相关数塔

给定一个数塔，如下图所示。在此数塔中，从顶部出发，在每一节点可以选择走左下或右下，一直走到底层。请找出一条路径，使路径上的数值和最大。 <table> <tbody>

朴灿烈づ我的快乐病毒、/ 2022年04月24日 11:34/ 0 赞/ 308 阅读

相关 HDU2084：数塔(DP)

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

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