POJ-1163-The Triangle-白红宇

POJ-1163-The Triangle

阅读量：804 次

发布时间：2023-03-03

本文共 867 字，大约阅读时间需要 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/

你可能感兴趣的文章