[文章目录]
Description
Mr. F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两座有同样高度的塔，使他们成为一座双塔，Mr. F可以从这N块水晶中任取M（1≤M≤N）块来搭建。但是他不知道能否使两座塔有同样的高度，也不知道如果能搭建成一座双塔，这座双塔的最大高度是多少。所以他来请你帮忙。
给定水晶的数量N（1≤N≤100）和每块水晶的高度Hi（N块水晶高度的总和不超过2000），你的任务是判断Mr. F能否用这些水晶搭建成一座双塔（两座塔有同样的高度），如果能，则输出所能搭建的双塔的最大高度，否则输出“Impossible”。
神一般的DP思路。（然而zty小同学运用4亿次运算加上各种优化，成功的躲过TLE）。
dp[i][j]表示前i个物品，建造的双塔高度差为j时的最高塔高，显然有四种情况：
1.NO.i物品不选，dp[i][j]=dp[i-1][j]。
2.将物品落到较矮的塔上，使矮塔比原高塔高j。
3.将物品落到较矮的塔上，使高度差减小到j（依然矮塔比高塔矮）
4.将物品落到高塔上，高度差增大了w[i].
各种小细节，特判数组越界 和 增高时的原情况是否存在。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int w[110],dp[110][1100];
int main()
{
scanf("%d",&n);
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=1000;j++)
{
dp[i][j]=dp[i-1][j];
if(w[i]>=j&&dp[i-1][w[i]-j]!=-1) dp[i][j]=max(dp[i-1][w[i]-j]+w[i]-j,dp[i][j]);
if(w[i]<=j) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]);
if(j+w[i]<=1000&&dp[i-1][j+w[i]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j+w[i]]+w[i]);
}
}
if(dp[n][0]!=0)printf("%d",dp[n][0]);
else puts("Impossible");
return 0;
}