POJ-1163-The Triangle-白红宇

POJ-1163-The Triangle

阅读量：793 次

发布时间：2023-03-03

本文共 872 字，大约阅读时间需要 2 分钟。

要解决这个问题，我们需要找到从三角形的顶点走到最底层时所能获得的最大值。每一步只能向左下方或右下方走。我们可以使用动态规划来解决这个问题。

思路

我们可以使用动态规划来解决这个问题。具体来说，我们从顶点开始，逐层计算每个点的最大值。每个点的值是其上方左右两个点中的较大者加上自身的值。这样，我们就能确保每一步都能得到最大的可能值。

代码

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
#include 
       
        
#include 
        
          #include 
         
           #include 
          
            using namespace std; typedef long long LL; const int MAXN = 100 + 10; int a[MAXN][MAXN]; int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) { cin >> a[i][j]; } } int res = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) { a[i][j] += max(a[i-1][j], a[i-1][j-1]); if (a[i][j] > res) { res = a[i][j]; } } } cout << res << endl; return 0; }

解释

输入读取：首先读取输入的三角形大小 n 和每个点的值。

初始化：我们使用一个二维数组 a 来存储每个点的值。

动态规划计算：从顶点开始，逐层计算每个点的最大值。每个点的值是其上方左右两个点中的较大者加上自身的值。

结果输出：在计算完所有点的值后，输出最大的值。

通过这种方法，我们可以高效地计算出从顶点走到最底层时的最大值。

转载地址：http://sbxfk.baihongyu.com/

你可能感兴趣的文章