noip2011 烟台加试赛

Question

塔（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。

Answer 1

第一眼是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

Answer 2

背包
dp算出每个容积的可能性
从(v/2)往0找