洛谷P1216数字三角形

冷不防 2022-04-15 05:05 146阅读 0赞

## 题目描述 ##

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

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

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大

## 输入输出格式 ##

**输入格式：**

第一个行包含 R(1<= R<=1000) ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

所有的被供应的整数是非负的且不大于100。

**输出格式：**

单独的一行,包含那个可能得到的最大的和。

## 输入输出样例 ##

**输入样例\#1：** 复制

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

**输出样例\#1：** 复制

30

1）//正序查找   最后一行取最大值

#include<iostream>
    using namespace std;
    int f[1005][1005];
    int a[1005][1005]={0};
    int main(){
    	int n,mmax=0;
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=i;j++)
    		 cin>>a[i][j];
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=i;j++){
    		  f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
    			mmax=max(f[i][j],mmax);
    		}
    	}
    	cout<<mmax<<endl;
    	return 0;
    }

2）//倒序查找  输出f\[1\]\[1\]

#include<iostream>
    using namespace std;
    int f[1010][1010];
    int a[1010][1010];
    int main(){
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=i;j++){
    			cin>>a[i][j];
    			f[i][j]=a[i][j];
    		}
    	}
    	for(int i=n-1;i>=1;i--){
    		for(int j=1;j<=i;j++)
    		 f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
    	}
    	cout<<f[1][1]<<endl;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关洛谷 P2602 [ZJOI2010]数字计数

![1596060-20190721202628330-676586515.png][] 又是一道数位DP，不过做题多了也就发现套路了，这道题注意对前导0的判断以及dp状态的

冷不防/ 2023年06月04日 07:59/ 0 赞/ 19 阅读

相关数字三角形（洛谷P1216题题解，C++语言描述）

题目要求 [题目链接][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_a

心已赠人/ 2022年11月07日 04:06/ 0 赞/ 156 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 273 阅读

相关洛谷P1307 数字反转

题目背景猪猪hanke得到了一只鸡题目描述猪猪Hanke特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke吃鸡很特别，为什么特别呢？因为他有10种配料（芥

ゝ一纸荒年。/ 2022年05月31日 00:55/ 0 赞/ 136 阅读

相关洛谷P1118 [USACO06FEB]数字三角形Backward Digit Su…

题目描述 FJ and his cows enjoy playing a mental game. They write down the numbers from 1

朴灿烈づ我的快乐病毒、/ 2022年05月30日 02:09/ 0 赞/ 158 阅读

相关洛谷P1216 [USACO1.5]数字三角形 Number Triangles

题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7

你的名字/ 2022年05月28日 21:19/ 0 赞/ 136 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 271 阅读

相关洛谷P1216数字三角形

题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7

冷不防/ 2022年04月15日 05:05/ 0 赞/ 147 阅读

相关 P1216 [IOI1994][USACO1.5]数字三角形 Number Triangles

题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7

待我称王封你为后i/ 2021年11月26日 07:31/ 0 赞/ 151 阅读

相关洛谷 P2034 选择数字

洛谷 P2034 选择数字 Description 给定一行n个非负整数a\[1\]..a\[n\]。现在你可以选择其中若干个数，但不能有超过k个连续的数字被

小咪咪/ 2021年11月10日 02:28/ 0 赞/ 196 阅读