信息学奥赛一本通T1288：动态规划的基本模型 三角形最佳路径问题

【题目描述】如下所示的由正整数数字构成的三角形：73 88 1 02 7 4 44 5 2 6 5从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。注意：路径上的每一步只能从一个数走到下一层上和它最近的下边(正下方)的数或者右边（右下方）的数。【输入】第一行为三角形高度100≥h≥1，同时也是最

信息学奥赛一本通T1288：三角形最佳路径问题

【题目描述】

如下所示的由正整数数字构成的三角形：

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的下边(正下方)的数或者右边（右下方）的数。

【输入】

第一行为三角形高度100≥h≥1，同时也是最底层边的数字的数目。

从第二行开始，每行为三角形相应行的数字，中间用空格分隔。

【输出】

最佳路径的长度数值。

【输入样例】

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

【输出样例】

30

【源程序】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 2520
#define E 1e-12
using namespace std;
int a[N][N],f[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];

    for(int i=n;i>=1;i--)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i+1][j]+a[i][j],f[i+1][j+1]+a[i][j]);

    cout<<f[1][1]<<endl;

    return 0;
}

 

信息学奥赛一本通T1288：动态规划的基本模型 三角形最佳路径问题 归属于 动态规划的基本模型，更多同类题解源程序见：动态规划的基本模型 和 三角形最佳路径问题

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！