noip2011烟台加试赛塔(tower.pas/c/cpp)问题描述小明很喜欢摆积木,现在他正在玩的积木是由N个木块组成的,他想用这些木块搭出两座高度相同的塔,一座塔的高度是搭建它的所有木块的高度

时间:2024-04-30 20:50:23 5A范文网 浏览: 平时作业 我要投稿

问题描述:

noip2011 烟台加试赛
塔(tower.pas/c/cpp)
【问题描述】
小明很喜欢摆积木,现在他正在玩的积木是由N个木块组成的,他想用这些木块搭出两座高度相同的塔,一座塔的高度是搭建它的所有木块的高度和,并且一座塔至少要用一个木块.每个木块只能用一次,也可以不用.目前已知每块木块的高度,小明想知道在最终两个塔的高度相同的情况下,他所能搭的塔的最大高度是多少,
【输入文件】
输入文件tower.in.第一行为一个整数N,表示木块个数.第二行是N个整数,表示N块木块的高度.
【输出文件】
输出文件towert.out.仅一个整数,表示能搭建的塔的最大高度,若不能搭建两座相同高度的塔,则输出“-1”.
【输入样例】
3
2 3 5
【输出样例】
5
【数据规模】
对于100%的数据,N≤50,每块木块的高度h满足1≤h≤500000,所有木块的高度总和≤500000.

最佳答案

第一眼是dp问题,然后思考终于找出状态转移.
A[k,p]表示前k个数(高度)组成差为p(p>0)的两个数的最大和
边界A[0,0]=0;
转移:A[k,p]=max(A[k-1,abs(p-h[k])],A[k-1,p+h[k]])+h[k];
就是求A[n,0]/2

来源:网络整理 免责声明:本文仅限学习分享,如产生版权问题,请联系我们及时删除。

相关文章:

计算机应用基础y 过程性评测(42)【参考答案】04-30

计算机应用基础y 过程性评测(37)【参考答案】04-30

计算机应用基础y 过程性评测(38)【参考答案】04-30

计算机应用基础y 过程性评测(39)【参考答案】04-30

计算机应用基础y 过程性评测(40)【参考答案】04-30

计算机应用基础y 过程性评测(41)【参考答案】04-30

计算机专业英语阅读y 过程性评测(3)【参考答案】04-30

计算机专业英语阅读y 过程性评测(4)【参考答案】04-30

计算机专业英语阅读y 过程性评测(5)【参考答案】04-30

计算机专业英语阅读y 过程性评测(6)【参考答案】04-30

热搜文章
最新文章