[vijos1037]搭建双塔

题目（vijos）
来说说这题吧。
首先，这肯定是一道dp题，那么就要先把状态定义好，以便转移。
用dp[i][j]表示第一座塔高度为i，第二座塔高度为j？
显然不好转移，因为只有当i==j时才有效。
而这道题和高度差有关：只有两座塔高度差为0时才算搭建成功。
那就这样定义：
dp[i][j]表示选到第i块水晶，两座塔的高度差为j时，低塔的最大高度。
这就很好转移了：转移分四种情况，
1.不选当前水晶
dp[i][j]=dp[i-1][j];
2.选择当前水晶，并将其放在高塔上
dp[i][j]=max(dp[i][j],dp[i-1][j+a[i]]);   //a[i]表示第i块水晶的高度
因为放在高塔上不影响低塔的高度，但高度差会增加a[i]。
3.选择当前水晶，并将其放在低塔上，但低塔不会变成高塔
dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]+a[i]);
既然不影响低塔与高塔的关系（即低塔还是原来那座塔，高塔还是原来那座塔），
那么高度差就会减小a[i]，低塔的最大高度会增加a[i]。
4.选择当前水晶，并将其放在低塔上，且低塔变高塔，高塔变低塔
dp[i][j]=max(dp[i][j],dp[i-1][a[i]-j]+a[i]-j);
这个用数学关系推一下吧：
设h1为原低塔高度，h2为原高塔高度，那么j=h2-h1，
然后h1加上a[i]，原方程变成：j-a[i]=h2-(h1+a[i])，
由于此时低塔超过高塔高度，则j-a[i]为负数，所以此时高度差为-(j-a[i])=a[i]-j，
低塔变高塔，高塔变低塔，那么此时低塔高度最大值就是原高塔的高度。
完毕。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n,h;
int a[105];
int dp[105][2005];
int ans;
int main()
{
	memset(dp,-0x7f,sizeof dp);
	dp[0][0]=0;
	scanf(
	for (int i=1;i<=n;++i)
		scanf(
	for (int i=1;i<=n;++i)
	{
		for (int j=h;j>=0;--j)
		{
			dp[i][j]=dp[i-1][j];
			dp[i][j]=max(dp[i][j],dp[i-1][j+a[i]]+a[i]);
			if (j>=a[i])
			 dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]);
			else
			 dp[i][j]=max(dp[i][j],dp[i-1][a[i]-j]+a[i]-j);
		}
	}
	if (!dp[n][0]) puts("Impossible");
	else printf(
	return 0;
}