ACM学习-POJ-1163-The Triangle

桃扇骨 2022-09-17 06:24 157阅读 0赞

**菜鸟学习ACM，纪录自己成长过程中的点滴。**

**学习的路上，与君共勉。**

**ACM学习-POJ-1163-The Triangle**

<table style="font-weight:bold; font-size:24px; color:rgb(255,0,0); font-family:Times"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center; font-size:18pt; font-weight:bold; color:blue">
      The Triangle 
    </div> 
    <div style="text-align:center; font-size:12pt"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;34125</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;20303</td> 
       </tr> 
      </tbody> 
     </table> 
    </div> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Description</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">  
     <pre>7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

(Figure 1)</pre>  Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.&nbsp; 
     <br> 
    </div> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Input</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is &gt; 1 but &lt;= 100. The numbers in the triangle, all integers, are between 0 and 99. 
    </div> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Output</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt">
      Your program is to write to standard output. The highest sum is written as an integer. 
    </div> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Sample Input</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5</pre> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Sample Output</p> <pre style="font-family:'Courier New',Courier,monospace; font-size:12pt">30</pre> <p style="text-align:left; font-size:18pt; font-weight:bold; color:blue"> Source</p> 
    <div style="font-family:'Times New Roman',Times,serif; font-size:12pt"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=IOI+1994" style="text-decoration:none" rel="nofollow">IOI 1994</a> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

题目要求：

输入一个n层的三角形，第i层有i个数，求从第1层到第n层的所有路线中，权值之和最大的路线。  
规定：第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。  
  
  
题目分析：

典型的动态规划。

因此我们可以从下往上推，相邻的两个数中找较大的与上层相加，得出的结果相邻的两个数中再找较大的与上层相加，以此类推。用二维数组arr\_\[\]\[\]记录从下到该点的最大值。

核心代码

arr\_\[i\]\[j\] += arr\_\[i+1\]\[j\] > arr\_\[i+1\]\[j+1\] ? arr\_\[i+1\]\[j\] : arr\_\[i+1\]\[j+1\];

最后的结果就是arr\_\[0\]\[0\]。

下面给出AC代码。

#include <stdio.h>
    #define MAXSIZE 105
    int main()
    {
        int n;
        int i, j;
        int arr_[MAXSIZE][MAXSIZE];
        while (~scanf("%d", &n))
        {
            for (i=0; i<n; i++)
            {
                for (j=0; j<=i; j++)
                {
                    scanf("%d", &arr_[i][j]);
                }
            }
            
            for (i=n-2; i>=0; i--)
            {
                for (j=0; j<=i; j++)
                {
                    arr_[i][j] += arr_[i+1][j] > arr_[i+1][j+1] ? arr_[i+1][j] : arr_[i+1][j+1];
                }
            }
            
            printf("%d", arr_[0][0]);
        }
        return 0;
    }