题目地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2059
题目大意是:给定n个立方体,去组成2个塔高度相同的塔,求能组成的双塔的最大高度是多少,立方体不必用完。
状态dp[i][j]为读取第i个立方体,双塔高度差为j时的,较高塔的高度的最大值。
显然dp[i][j]读取第i个立方体时有3中情况:
1)即不放在较高的塔上,也不放在较低的塔上
2)放在较高的塔上
3)放在较低的塔上,分两中情况,1.低塔的高度超过高塔,2.低塔的高度还是低于高塔
对应上述三中情况对应的状态转换是
1)dp[i][j]=max(dp[i-1][j],dp[i][j]);
2) dp[i][j]=max(dp[i-1][j-h[i]]+h[i],dp[i][j]);(注意,必须j>h[i])
3) 1.dp[i][j]=max(dp[i-1][h[i]-j]+j,dp[i][j]);(注意,必须j<h[i])
2.dp[i][j]=max(dp[i-1][j+h[i]],dp[i][j]);
最后注意边界处理!!
zoj_2059.cpp:
分享到:
相关推荐
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
zoj吐血制作,希望大家喜欢
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj4041正确题解源代码,以及运行程序
浙江大学ZOJ源码题解,按照题目类型和难易分类。
acm中zoj1002的可运行C++程序
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
一个非常非常非常非常实用的zoj结题代码
zoj的代码实现,很好,而且很全面,全部实现。
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
zoj 2536 这个不是用贪心做的
浙大acm OJ1204,自己做的,已经AC 分享一下,若有更好的算法可以教教我
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
能AC 通过的c++代码,包括zoj1002,1091,1789
浙江大学zoj题目代码,大量水题代码,齐全
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告