小易有n块砖块，每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。为了让问题简单，砖块堆砌就是简单的高度相加，某一块砖只能使用在一座塔中一次。小易现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。
输入描述:
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)，即一共有n块砖块
第二行为n个整数，表示每一块砖块的高度height[i] (1 ≤ height[i] ≤ 500000)
输出描述:
如果小易能堆砌出两座高度相同的塔，输出最高能拼凑的高度，如果不能则输出-1.
保证答案不大于500000。
输入例子:
3
2 3 5
输出例子:
5
分析：
状态：d[i][j]代表前i块砖，高度差为j，矮的那堆的高度。
状态转移：
决策1：不放。
d[i][j]=d[i-1][j];
决策2：放在矮的那堆，放上去后高度比原来高的矮。
d[i][j]=d[i-1][j+a[i]]+a[i];
决策3：放在矮的那堆，放上去后高度比原来高的高。
d[i][j]=d[i-1][a[i]-j]+a[i]-j;
决策4：放在高的那堆上
d[i][j]=d[i-1][j-a[i]];
边界值d[0][i]=-1, d[0][0]=0
最后输出的时候要注意一下，如果结果为0，要输出-1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxh=500000+5;
int a[55];
int d[2][maxh];
int main()
{
//freopen("in.txt","r",stdin);
int n;
int sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
memset(d[0],-1,sizeof(d[0]));
d[0][0]=0;
int t=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=sum;j++)
{
d[t][j]=d[t^1][j];
if(j+a[i]<=sum && d[t^1][j+a[i]]>=0)
d[t][j]=max(d[t][j],d[t^1][j+a[i]]+a[i]);
if(a[i]-j>=0 && d[t^1][a[i]-j]>=0)
d[t][j]=max(d[t][j],d[t^1][a[i]-j]+a[i]-j);
if(j-a[i]>=0 && d[t^1][j-a[i]]>=0)
d[t][j]=max(d[t][j],d[t^1][j-a[i]]);
}
t^=1;
}
printf("%d\n",d[t^1][0]==0? -1:d[t^1][0]);
return 0;
}