10303 数字三角(必做)
时间限制:1000MS 内存限制:65535K
提交次数:117 通过次数:56
题型: 编程题 语言: C++;C;VC;JAVA
Description
问题描述:给定一个由n行数字组成的数字三角形,如下图所示。试用动态规划算法,计算出从三角顶部至底部的一条路径,使得该路径经过的数字总和最大。 注意每个数字只能走向下一行左边或右边的数字,而不能跳跃的走。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行是数字三角的行数n,1<=n<=100。接下来n行是数字三角各行中的数字,所有数字在0~99之间。
输出格式
输出两行,第一行是计算出的最大路径的和值,第二行是该路径上的数字。若有多条路径,靠右的路径优先(即仅仅输出靠右的路径即可,无需多条路径都输出)。 如: Input: 5 7 3 8 8 1 6 2 7 4 4 4 5 2 4 5 有两条路径:7-3-8-7-5和7-8-6-4-5都为30,由于后者靠右,因此仅输出后者。 Output: 30 7 8 6 4 5
输入样例
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
#include <iostream>
#include <stdio.h>
using namespace std;
int n;
int a[10000][10000],b[10000][10000]; //记录数据 、 记录计算的和 1<=n<=100
void findP(){
for(int i=n;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
if(j==n) b[i][j]= a[i][j]; //底层节点值和 = 本身节点值
else {
if(b[i+1][j]>b[i+1][j+1]) //本节点值和 =取下一层子树值和的最大值 + 本节点值
b[i][j] = b[i+1][j] + a[i][j];
else
b[i][j] = b[i+1][j+1] + a[i][j];
}
}
}
}
int main()
{
freopen("in.txt","r",stdin);
cin >>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin >> a[i][j];
findP();
cout<< b[1][1]<<endl;
cout << a[1][1];
int temp = b[1][1]-a[1][1];
for(int i=2;i<=n;i++)
{
for(int j=i;j>=1;j--) //靠右的路径优先
{
if(b[i][j]==temp) //一一匹配
{
cout << " " <<a[i][j];
temp-=a[i][j]; //更新每一层的匹配值
break; //进入下一层循环
}
}
}
return 0;
}
相关推荐
接下来n行是数字三角各行中的数字,所有数字在0~99之间。 输出格式 输出两行,第一行是计算出的最大路径的和值,第二行是该路径上的数字。若有多条路径,靠右的路径优先(即仅仅输出靠右的路径即可,无需多条路径都...
Problem B:数字三角形问题 Description 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形 的顶至底的一条路径,使该路径经过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 ...
编程任务:对于给定的由n 行数字组成的数字三角形,编程计算从三角形的顶至底的路径经过的数字和的最大值。 Input 输入数据是由多组测试数据组成。第1 行是数字三角形的行数n,1≤n≤100。接下来n行是数字三角形...
接下来n行是数字三角各行中的数字,所有数字在0~99之间。 输出格式 输出两行,第一行是计算出的最大路径的和值,第二行是该路径上的数字。若有多条路径,靠右的路径优先(即仅仅输出靠右的路径即可,无需多条路径...
这是使用VC6.0实现的解决数字三角形的程序,寻找一条路径使路径上的数值和最小
问题描述:给字一个由n行数字组成的数字三角形,如图3-7所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 ★算法设计:对于给定的由n行数字组成的数字三角形,计算从三角形的...
给定一个由n行数字组成的数字三角形,如下图所示。 试设计一个算法,计算出从三角形的顶部至底部的一条路径,使得该路径上经过的数字总和值最大。
数字三角形 c++
数字三角形中的数字为不超过100的整数。现规定从最顶层走到最底层,每一步可沿左斜线向下或右斜线向下走。 任务一:假设三角形行数≤10,键盘输入一个确定的整数值M,编程确定是否存在一条路径,使得沿着该路径所...
数字三角形(C语言编写) 算法
C++写的,利用动态规划解决数字三角形问题,含.cpp文件一个。
数字三角形动态规划 使用C语言来实现 具体就是使用动态规划技术来编程
VB 数字三角 VB 数字三角 VB 数字三角 VB 数字三角
纯C++编写,并且提供input()输入,output()输出,保证运行成功!
数字三角形.-动态规划,思路新颖易懂
本题是关于算法分析设计的一个题目。给定一个有n行数字组成的数字三角形,如图所示,试设计一个算法,计算出三角形顶至底的一条路径,使该路径经过的数字总和最大。
信息奥赛课课通P174-1,蛇形数字三角形的C++程序代码。
接下来n行是数字三角各行中的数字,所有数字在0~99之间。 输出格式 输出两行,第一行是计算出的最大路径的和值,第二行是该路径上的数字。若有多条路径,靠右的路径优先(即仅仅输出靠右的路径即可,无需多条路径...
利于Multisim11模拟的数字三角波发生器
数字三角形 基于C实现的N阶数字正方形 ;N阶数字三角形;N阶数字递减三角形;乘法表