HDU 2084 数塔 (dp)
2024-08-27 17:28:14
Problem Description
在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的:
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
已经告诉你了,这是个DP的题目,你能AC吗?
Input
输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。
Output
对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。
Sample Input
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
分析:
数塔的题应该从下往上找,这样找到最后的话就只有一个最大值,而且这样还有利于输出路径。
代码:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int N;
scanf("%d",&N);
while(N--)
{
int n,a[100][100]= {0},b[100][100]= {0},i,j;
scanf("%d",&n);
for(i=0; i<n; i++)
for(j=0; j<=i; j++)
{
scanf("%d",&a[i][j]);
b[i][j]=a[i][j];
}
for(i=n-2; i>=0; i--)
for(j=0; j<=i; j++)
{
if(b[i+1][j]>b[i+1][j+1])
b[i][j]+=b[i+1][j];
else
b[i][j]+=b[i+1][j+1];
}
int max1=b[0][0],a1,b1;
printf("%d\n",max1);
/*路径的输出
for(i=0; i<n; i++)
{
for(j=0; j<=i; j++)
{
if(a[i][j]+b[i+1][j]==max1)
{
a1=i;
b1=j;
max1=b[i+1][j];
break;
}
else if(a[i][j]+b[i+1][j+1]==max1)
{
a1=i;
b1=j;
max1=b[i+1][j+1];
break;
}
}
if(a1==0&&b1==0)
printf("(0,0)");
else
printf("-->(%d,%d)",a1,b1);
}
printf("\n");
*/
}
return 0;
}
最新文章
- linq和lanmbda表达式比较解析
- 使用culr
- uva 1152 4 values whose sum is zero ——yhx
- 一张图看懂360&#176;全景和VR的区别
- C++ Language
- 【redis】 linux 下redis 集群环境搭建
- [转]p2p端口映射工具 dog-tunnel
- .net版本之间的关系
- Linux的文件属性
- vc获取时间戳
- java提高篇(二二)-----LinkedList
- 做一个项目前搭建一个tabBar(一)框架
- js中的伪数组
- 记录Redis使用中遇到的两个问题(原子性及数据完整性)
- 【转载】 Pytorch(0)降低学习率torch.optim.lr_scheduler.ReduceLROnPlateau类
- Linux平台安装Oracle11gR2数据库
- TMS320VC5509的MCBSP配置成SPI模式通信
- JVM调优系列:(五)JVM常用调试参数和工具
- 初步总结javascript中学习DOM之前的知识
- python中mysql的存储
热门文章
- 分享几个.Net计划任务组件
- Android Camera多屏幕适配解决预览照片拉伸
- [OS] 多线程--原子操作 Interlocked系列函数
- [STL] 如何将一个vector赋给另一个vector
- css样式 一定要reset?
- java map的键是唯一的 所有 用set类型存放
- 前端基础:JavaScript BOM对象
- hadoop中DataNode消失挂掉的原因及解决方法
- bzoj 3275: Number (最小割)
- Codeforces Round #469 (Div. 2) E. Data Center Maintenance