NYOJ 18 The Triangle 填表法,普通dp
2024-08-29 22:27:22
题目链接:
http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=18
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 分析:
dp[i][j]=f_max(dp[i+1][j],dp[i+1][j+1])+a[i][j]; 代码如下:#include<bits/stdc++.h>
#define pai 3.1415926535898
using namespace std;
int f_max(int a,int b)
{
if(a>b)
{
return a;
}else
{
return b;
}
}
int main()
{
int n;
scanf("%d",&n);
int a[n][n];
memset(a,,sizeof(a));
for(int i=;i<n;i++)
{
for(int j=;j<=i;j++)
{
scanf("%d",&a[i][j]);
}
}
int dp[n][n];
memset(dp,,sizeof(dp));
for(int j=;j<n;j++)
{
dp[n-][j]=a[n-][j];
}
for(int i=n-;i>=;i--)
{
for(int j=;j<=i;j++)
{
dp[i][j]=f_max(dp[i+][j],dp[i+][j+])+a[i][j];
}
}
printf("%d\n",dp[][]);
return ;
}
最新文章
- react+react-router+webpack+express+nodejs
- 如何Recycle一个SharePoint Web Application,以及为什么
- java: system.gc()和垃圾回收机制finalize
- SQL server 常用语句
- Lua学习----Lua的表达式
- vertical-align 垂直居中
- 【USACO 1.4】Arithmetic Progressions
- LAMP网站架构方案分析
- Codeforces Round #Pi (Div. 2)
- DataSetToList 和 DataTableTolist 转换
- iphone抓取移动网络报文的方法
- hdu1395-2^x mod n = 1
- FutureTask分析(1.8)
- js 科学计数法 转换为 数字字符 突破幂数正数21位,负数7位的自动转换限制
- Sql 关于 查俩个表 第二个表用到第一个表的某一个数据
- 如何在eclipse中配置反编译工具JadClipse
- mac 下终端 操作svn命令 以及出现证书错误的处理方法
- sqlserver 表循环-游标、表变量、临时表
- kubernetes 简单yaml文件运行例子deployment
- 【iCore4 双核心板_uC/OS-II】例程六:信号量——任务同步