首页 > 代码库 > HDU 2084 数塔(DP初步应用)
HDU 2084 数塔(DP初步应用)
HDU 2084 数塔
在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的:
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
已经告诉你了,这是个DP的题目,你能AC吗?
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?
已经告诉你了,这是个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值,然后从最后一行开始往上层层递进。#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int a[105][105], d[105][105]; int main() { int n; scanf("%d\n", &n); while (n--) { memset(a, 0, sizeof(a)); memset(d, 0, sizeof(d)); int m; scanf("%d\n", &m); int t = m; int cnt = 1; while (t--) { for (int i = 1; i <= cnt; i++) { scanf("%d", &a[cnt][i]); } cnt++; } for (int i = 1; i <= m; i++) { d[m][i] = a[m][i]; } for (int i = m - 1; i >= 1; i--) { for (int j = 1; j <= i; j++) { d[i][j] = a[i][j] + max(d[i + 1][j], d[i + 1][j + 1]); } } printf("%d\n", d[1][1]); } return 0; }
HDU 2084 数塔(DP初步应用)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。