塔
Description
给出N个木块，告诉你每个木块的高度，你要用这些木块搭出两座高度相同的塔，一个塔的高度为搭建它的木块的高度之和，并且一个塔至少要用一个木块。木块只能用一次，也可以不用。问在这两座塔高度相同的条件下，能够搭出的塔的最大高度是多少？
Input
第一行一个整数N（N<=50）,表示木块的个数；
第二行N个整数，表示N个木块的高度。
每个木块的高度范围[1,500000],所有木块的高度总和<=500000。
第二行N个整数，表示N个木块的高度。
每个木块的高度范围[1,500000],所有木块的高度总和<=500000。
Output
一个数，表示能搭建的塔的最高高度，若不能搭建两座相同的塔，则输出-1.
Sample Input
| Original | Transformed |
3 2 3 5
Sample Output
| Original | Transformed |
5
动态规划题目
f[i,j]表示前i个分成高度差为j的两个塔时的最大高度
f[i,j]=max{f[i-1,j], f[i-1,j+a[i]], f[i-1,j-a[i]]+a[i](j-a[i]>=0)，f[i-1,abs(j-a[i])]-abs(j-a[i])+a[i](j-a[i]<0)}
答案就是f[n,0]
由于数据范围比较大，要用滚动数组减少使用内存。
#include<cstdio>
#include<cstring>
using namespace std;
int a[55],dp[2][1000005]={0};
#define max(a,b) (a)>(b)?(a):(b)
#define abs(a) (a)<0?(-a):(a)
#define inf ((1<<31)-1)
int main()
{
int n;
for(; ~scanf("%d",&n);)
{
int temp=0,summ=0;
for(int i=1; i<=n; ++i)
{
scanf("%d",&a[i]);
summ+=a[i];
}
if(n<=1)
{
printf("%d\n",-1);
continue;
}
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int i=1; i<=n; ++i)
{
for(int j=0; j<=summ; ++j)
{
dp[i%2][j]=dp[(i-1)%2][j];
if(j == a[i])
dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j - a[i]] + a[i]);
if(j < a[i] && dp[(i-1)%2][a[i] - j] -a[i] + j >= 0)
dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][a[i] - j] + j);
if(j > a[i] && dp[(i-1)%2][j - a[i]] + a[i] - j >= 0)
dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j - a[i]] + a[i]);
if(j + a[i] <= summ)
dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j + a[i]]);
}
}
temp=((dp[n%2][0]==0)?-1:(dp[n%2][0]));
printf("%d\n",temp);
}
return 0;
}