nyoj 18 The Triangle
2024-08-24 15:17:59
The Triangle
时间限制:1000 ms | 内存限制:65535 KB
难度:4
- 描述
-
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.- 输入
- Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but
<= 100. The numbers in the triangle, all integers, are between 0 and 99. - 输出
- Your program is to write to standard output. The highest sum is written as an integer.
- 样例输入
-
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 - 样例输出
-
30
#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
int n,maxx=0,num[105][105]= {0};
scanf("%d",&n);
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++)
scanf("%d",&num[i][j]);
for(int i=2; i<=n; i++)
{
for(int j=1; j<=i; j++)
{
num[i][j]=num[i][j]+max(num[i-1][j],num[i-1][j-1]);
}
}
for(int i=1; i<=n; i++)
if(num[n][i]>maxx)
maxx=num[n][i];
printf("%d\n",maxx);
return 0;
}
//#include<stdio.h>
//#include<string.h>
//#include<algorithm>
//using namespace std;
//
//int n,dp[110][110],map[110][110];
//
//int dfs(int i,int j)
//{
// if(dp[i][j]!=-1)
// return dp[i][j];
// if(i==n) dp[i][j]=map[i][j];
// else
// {
// int x=dfs(i+1,j);
// int y=dfs(i+1,j+1);
// dp[i][j]=max(x,y)+map[i][j];
// }
// return dp[i][j];
//}
//int main()
//{
// int i,j;
// scanf("%d",&n);
// for(i=1; i<=n; i++)
// {
// for(j=1; j<=i; j++)
// {
// scanf("%d",&map[i][j]);
// dp[i][j]=-1;
// }
// }
// printf("%d\n",dfs(1,1));
// return 0;
//} //#include <stdio.h>
//#include <algorithm>
//using namespace std;
//int main()
//{
// int n,num[105][105]= {0};
// scanf("%d",&n);
// for(int i=1; i<=n; i++)
// for(int j=1; j<=i; j++)
// scanf("%d",&num[i][j]);
// for(int i=n-1; i>=0; i--)
// for(int j=1; j<=i; j++)
// num[i][j]=num[i][j]+max(num[i+1][j],num[i+1][j+1]);
// printf("%d\n",num[1][1]);
// return 0;
//}
//
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; int n;
int dp[110][110],map[110][110]; int d(int i,int j)
{
if(dp[i][j]>=0) return dp[i][j];
return dp[i][j]=map[i][j]+(i==n?0:(d(i+1,j)>d(i+1,j+1)?d(i+1,j):d(i+1,j+1)));
} int main()
{
while(~scanf("%d",&n))
{
int i,j;
for(i=1; i<=n; i++)
{
for(j=1; j<=i; j++)
{
scanf("%d",&map[i][j]);
dp[i][j]=-1;
}
}
int ans=d(1,1);
printf("%d\n",ans);
}
return 0;
}
最新文章
- css之盒模型
- struts2学习笔记--struts.xml配置文件详解
- spring mvc+ spring +mybatis
- js文件被浏览器缓存的思考
- Leetcode | Valid Sudoku &; Sudoku Solver
- poj 1190 生日蛋糕
- Mapreduce中的字符串编码
- TM4C123GH6PM程序
- HBase笔记--自定义filter
- 《JavaScript高级程序设计》读书笔记 ---Date 类型
- Beamer中左边画图, 右边文字解释
- SSH 和 Git
- docker的安装与启动
- Hexo+Github搭建博客问题
- H - An Easy Problem?!
- html5本地存储技术 localstorage
- List 的一个有用的高效的操作 removeAll
- eclipse如何恢复误删文件
- jvm linux 时区设置
- java 加载过程
热门文章
- C# 实现java中 wiat/notify机制
- http://www.cnblogs.com/kkdn/
- matlab实现cart(回归分类树)
- NYOJ 925 国王的烦恼 (并查集)
- Linux 脚本内容指定用户执行
- Feather包实现数据框快速读写,你值得拥有
- elk系列1之入门安装与基本操作【转】
- TreeSet之定制排序和自然排序
- 7.Python3标准库--文件系统
- postman中 form-data、x-www-form-urlencoded、raw、binary的区别 &;&; 下载文件