dp46上 HDU2084
Input 输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间 0,99 0,99内。 Output 对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。 Sample Input Sample Output
发布日期:2021-06-29 21:39:36
浏览次数:3
分类:技术文章
本文共 904 字,大约阅读时间需要 3 分钟。
在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少? 已经告诉你了,这是个DP的题目,你能AC吗?
1573 88 1 0 2 7 4 44 5 2 6 5
30
代码:
#include<cstdio>
#include<algorithm> #include<cstring> #include<queue> #include<map> #include<set> typedef long long LL; const int maxn=105; using namespace std; int main() { int i,j,n,t; int dp[maxn][maxn],a[maxn][maxn]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { scanf("%d",&a[i][j]); } } memset(dp,0,sizeof(dp)); for(j=1;j<=n;j++) dp[n][j]=a[n][j];//边界问题,将行赋值给dp数组 for(i=n-1;i>=1;i--)//一定是逆序枚举的 for(j=1;j<=i;j++) dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);//取左下右下较大着 printf("%d\n",dp[1][1]);//由于逆序枚举,所以答案是dp[1][1]; } return 0; }转载地址:https://dh-butterfly.blog.csdn.net/article/details/70159994 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月24日 06时10分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
外贸邮箱选择,外贸企业邮箱注册,海外邮箱申请
2019-04-30
哪家企业邮箱好?免费企业邮箱来一个?邮件服务器谁家好用?
2019-04-30
企业邮箱大全,企业邮箱查询,最大的邮箱是哪个?
2019-04-30
企业邮箱怎么注册流程?企业邮箱域名怎么注册?
2019-04-30
企业电子信箱,电子邮箱格式,企业邮箱怎么注册?
2019-04-30
如何申请企业邮箱注册,如何购买邮箱?
2019-04-30
购买企业邮箱,哪个邮箱最好用?邮件撤回怎么操作?
2019-04-30
电子邮箱是什么?如何申请电子邮箱,申请电子邮箱好处
2019-04-30
如何注册海外邮箱?如何进行邮箱注册163,这些技巧交给你
2019-04-30
企业邮件注册,手机怎么注册邮箱?
2019-04-30
【转载】舍弃 Python+C,Salesforce 将企业级软件全面迁移到 Go 语言
2019-04-30
ConnectorStartFailedException
2019-04-30
Windows上配置Gradle环境
2019-04-30
maven 多层次pom 新引入包,编译成功,还是没有将包引入到本地
2019-04-30
leetCode2 两数相加
2019-04-30
【工具使用】使用pip与conda安装、更新与卸载Pytorch和torchvision
2019-04-30