数塔
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 41852 Accepted Submission(s): 24820
有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少? 已经告诉你了,这是个DP的题目,你能AC吗?
#include<stdio.h>
int main()
{
int C,i,j,N;
int a[][];
while(scanf("%d",&C)==)
{
while(C--)
{
scanf("%d",&N);
for(i=;i<N;i++)
for(j=;j<=i;j++)
scanf("%d",&a[i][j]);
for(i=N-;i>=;i--)
{
for(j=;j<=i;j++)
{
if(a[i][j]+a[i-][j]>a[i][j+]+a[i-][j])
a[i-][j]=a[i][j]+a[i-][j];
else
a[i-][j]=a[i][j+]+a[i-][j];
}
}
printf("%d\n",a[][]);
}
}
return ;
}
以上这种是别人的想法,下面我来说说我对DP的理解!
解题思路:
用二维数组存放数字三角形。
D( r, j) : 第r行第 j 个数字(r,j从1开始算)
MaxSum(r, j) : 从D(r,j)到底边的各条路径中,
最佳路径的数字之和。
问题:求 MaxSum(1,1)
典型的递归问题。
D(r, j)出发,下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形:
if ( r == N)
MaxSum(r,j) = D(r,j)
else
MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)
并且每算出一个MaxSum(r,j)就保存起来,下次用
到其值的时候直接取用,则可免去重复计算。那么
可以用O(n 2 )时间完成计算。因为三角形的数字总
数是 n(n+1)/2!
#include <bits/stdc++.h>
using namespace std;
int dp[][];
int maxSum[][];
int n;
int MaxSum(int i,int j)
{
if(maxSum[i][j]!=-)
return maxSum[i][j];
if(i==n)
maxSum[i][j]=dp[i][j];
else
{
int x=MaxSum(i+,j);
int y=MaxSum(i+,j+);
maxSum[i][j]=max(x,y)+dp[i][j];
}
return maxSum[i][j];
}
int main()
{
int T;
while(cin>>T)
{
while(T--)
{
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
{
cin>>dp[i][j];
maxSum[i][j]=-;
}
cout<<MaxSum(,)<<endl;
}
}
return ;
}
HDU 2084 数塔(简单DP入门)的更多相关文章
-
hdu 2084 数塔 (简单dp)
http://acm.hdu.edu.cn/showproblem.php?pid=2084 数塔 Time Limit: 1000/1000 MS (Java/Others) Memory L ...
-
HDU 2084 数塔 (dp)
题目链接 Problem Description 在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数 ...
-
HDU 2084 数塔 (DP)
数塔 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Pr ...
-
hdu 2084 数塔(简单dp)
题目 简单dp //简单的dp #include<stdio.h> #include<string.h> #include<algorithm> using nam ...
-
题解报告:hdu 2084 数塔(递推dp)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2084 Problem Description 在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这 ...
-
HDU 2084 数塔(动态规划)
数塔 http://acm.hdu.edu.cn/showproblem.php?pid=2084 Problem Description 在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描 ...
-
HDOJ.2084 数塔(DP)
数塔 点我挑战题目 题意分析 DP的思想,自上而下计算. [这几天比较忙 有空补上] 代码总览 /* Title:HDOJ.2084 Author:pengwill Date:2017-1-14 */ ...
-
ACM 杭电HDU 2084 数塔 [解题报告]
数塔 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submissi ...
-
HDU 2084 数塔 (动态规划DP)
原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=2084 题目分析:此题采用动态规划自底向上计算,如果我们要知道所走之和最大,那么最后一步肯定是走最后一排 ...
随机推荐
-
elasticsearch客户端连接选择
elasticsearch支持两种协议: http协议. Native Elasticsearch binary protocol(本地elasticsearch二进制协议):elasticsearc ...
-
php的rss订阅
一般来说我们很少自己造*,读取rss还是用git上的开源库吧 https://github.com/dg/rss-php 这个开源库不能读取博客园的rss订阅,新浪微博的格式显示有问题. 博客园的订 ...
-
[AngularJS] Introduction to ui-router
Introduce to basic $stateProvider.state() with $stateParams services. Understand how nested router w ...
-
CollapsingToolbarLayout
CollapsingToolbarLayout作用是提供了一个可以折叠的Toolbar,它继承至FrameLayout,给它设置layout_scrollFlags,它可以控制包含在Collapsin ...
-
SyntaxError: Non-ASCII character '\xe2' in file 编码错误
Editing .py file in the Notepad: But when run in the PowerShell, I found the follwing error: It seem ...
-
CSS的使用方法
参考资料:http://css.cuishifeng.cn/ 一.CSS的四种引入方式 1.行内式 行内式是在标记的style属性中设定CSS样式.这种方式没有体现出CSS的优势,不推荐使用(与链接式 ...
-
[Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?
这道题真的超级...毒瘤 + 卡常 + 耗 RP 啊... 传送门 noteskey 题解看 shadowice 大仙 的 code 如果发现自己 T 掉了,别心急,洗把脸再交一遍试试... //by ...
-
UVA215-Spreadsheet Calculator(模拟+拓扑排序)
Problem UVA215-Spreadsheet Calculator Accept:401 Submit:2013 Time Limit: 3000 mSec Problem Descript ...
-
vue深入响应式原理
vue深入响应式原理 深入响应式原理 — Vue.jshttps://cn.vuejs.org/v2/guide/reactivity.html 注意:这里说的响应式不是bootsharp那种前端UI ...
-
Ubuntu 上安装QTAV第三方视频库
安装QtAV的基本环境: sudo apt-get install build-essential sudo apt-get install libgl1-mesa-dev sudo apt-get ...