Description

2001年9月11日，一场突发的灾难将纽约世界贸易中心大厦夷为平地，Mr. F曾亲眼目睹了这次灾难。为了纪念“9·11”事件，Mr. F决定自己用水晶来搭建一座双塔。

Mr. F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两座有同样高度的塔，使他们成为一座双塔，Mr. F可以从这N块水晶中任取M（1≤M≤N）块来搭建。但是他不知道能否使两座塔有同样的高度，也不知道如果能搭建成一座双塔，这座双塔的最大高度是多少。所以他来请你帮忙。

给定水晶的数量N（1≤N≤100）和每块水晶的高度Hi（N块水晶高度的总和不超过2000），你的任务是判断Mr. F能否用这些水晶搭建成一座双塔（两座塔有同样的高度），如果能，则输出所能搭建的双塔的最大高度，否则输出“Impossible”。

Input Format

输入第一行为一个数N，表示水晶的数量。第二行为N个数，第i个数表示第i个水晶的高度。

Output Format

输出仅包含一行，如果能搭成一座双塔，则输出双塔的最大高度，否则输出一个字符串“Impossible”。

Sample Input

5
1 3 4 5 2

Sample Output

7

【题解】

动态规划，设$f[i,j]$表示，到第$i$个水晶，两个塔高度差$j$，高塔的最高高度。

那么$f[i,j]=f[i-1,j]$（不用这块水晶）

$f[i,j]=max(f[i,j],f[i-1,j-h[i]]+h[i]) (0 \leq j-h[i])$（用这块水晶叠到高塔上）

$f[i,j]=max(f[i,j],f[i-1,j+h[i]]) (j+h[i] \leq total_h)$ （用这块水晶叠到矮塔上，但是矮塔还是矮塔）

$f[i,j]=max(f[i,j],f[i-1,h[i]-j]+j) ( 0 \leq h[i]-j)$ （用这块水晶叠到矮塔上，矮塔变成高塔）

那么就可以写代码啦

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n,h[101],f[101][2010],tt;
int main() {
	int i;memset(f,-1,sizeof(f));
	for(scanf("%d",&n),i=1;i<=n;++i)scanf("%d",&h[i]),tt+=h[i];
	for (f[0][0]=0,i=1;i<=n;++i) {
		for (int j=0;j<=tt;++j) {
			if(f[i-1][j]>=0) f[i][j]=f[i-1][j];
			if(j-h[i]>=0&&f[i-1][j-h[i]]>=0) f[i][j]=max(f[i][j],f[i-1][j-h[i]]+h[i]);
			if(h[i]-j>=0&&f[i-1][h[i]-j]>=0) f[i][j]=max(f[i][j],f[i-1][h[i]-j]+j);
			if(j+h[i]<=tt&&f[i-1][j+h[i]]>=0) f[i][j]=max(f[i][j],f[i-1][j+h[i]]);
		}
	}
	if(f[n][0]>0)printf("%d\n",f[n][0]);else puts("Impossible");
}