题解报告:hdu 2084 数塔(递推dp)
2024-09-04 23:59:34
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2084
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
解题思路:这是一道动态规划的入门题目,比较简单。定义二维数组dp[i][j]的值保存该点到第n层的最大数字和。我们要做的就是通过比较dp[i+1][j]与dp[i+1][j+1]这两个谁大就取谁,让其与D[i][j]本身的权值相加即可。这样从下往上推,最后归于顶点。
状态转移方程为dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+D[i][j].
AC代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
int C,N,dp[][],D[][];//递推法,递归会超时
cin>>C;
while(C--){//测试实例的个数
cin>>N;//数塔的高度
memset(dp,,sizeof(dp));//清0
memset(D,,sizeof(D));
for(int i=;i<N;i++)
for(int j=;j<=i;j++)
cin>>D[i][j];//读入直角三角形数塔
for(int i=N-;i>=;i--)//从最低层往上递推
for(int j=;j<=i;j++)
dp[i][j]=max(dp[i+][j],dp[i+][j+])+D[i][j];//取下一层一个和它的右边一个最大的+当前的值
cout<<dp[][]<<endl;//输出最上层即为最大的数字和
}
return ;
}
最新文章
- YII 2.x 模板文件的 beginBlock、beginContent、beginCache
- Nginx 和 Apache 开启目录浏览功能
- codeforces Expecting Trouble
- MFC 窗口分割
- ACE的 日志
- 【iOS】iOS之Button segue弹出popOver消除(dismiss)问题
- 基于简单sql语句的sql解析原理及在大数据中的应用
- C语言的本质(22)——C标准库之字符串操作
- 简约才是王道? CardView 的使用
- 《HelloGitHub》第 35 期
- python高级-面向对象特性(12)
- OS + Linux RedHat 7 / redhat 7 configuration
- [svc]证书学习索引
- vue的.vue文件是怎么run起来的(vue-loader)
- 20155326刘美岑 《网络对抗》Exp1 PC平台逆向破解
- Mysql 数据库修改datadir和调整默认引擎要注意的问题
- myEtherWallet在线钱包的使用
- kvm虚拟化一: 图形化的管理方式
- 一个页面从输入URL 到页面加载显示完成,这个过程中都发生了什么?
- 【CSS3】好玩的动画线框
热门文章
- Client使用c#和odp.net连接server oracle
- atomic原子操作
- Android之怎样实现滑动页面切换【Fragment】
- SpringBoot初始教程之项目结构(一)
- Qt布局管理器的使用(一)
- Hibernate也须要呵护——Hibernate的泛型DAO
- css的白富美
- Android Studio运行app时提示Error: Please select Android SDK
- leetcode 395. Longest Substring with At Least K Repeating Characters
- Linux内核--基于Netfilter的内核级包过滤防火墙实现