链接:点我
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int v = + ;
const int MaxN = + ;
int N, sum, num[MaxN], dp[][v];
int main() {
int i, j, k;
cin >> N;
for(i = ; i < N; ++i) {
cin >> num[i];
sum += num[i];
}
memset(dp, -, sizeof(dp));
dp[][] = ;
int a;
for(i = ; i < N; ++i) {
a = i % ;
memset(dp[a], -, sizeof(dp[a]));
for(j = ; j <= sum; ++j) {
//1.不放第i块水晶;
if(dp[a ^ ][j] > -)
dp[a][j] = dp[a ^ ][j];
//2.放进去后,高塔变矮塔(第i块放在矮塔上了);
if(num[i] > j && dp[a ^ ][num[i] - j] > -)
dp[a][j] = max(dp[a][j], dp[a ^ ][num[i] - j] + j);
//3.放进去后,高塔仍高(第i块放在矮塔上);
if(j + num[i] <= sum && dp[a ^ ][j + num[i]] > -)
dp[a][j] = max(dp[a][j], dp[a ^ ][j + num[i]]);
//4.放进去后,高塔更高(第i块放在高塔上).
if(j >= num[i] && dp[a ^ ][j - num[i]] > -)
dp[a][j] = max(dp[a][j], dp[a ^ ][j - num[i]] + num[i]);
}
}
if(dp[a][] > )
cout << dp[a][] << endl;
else
cout << "Impossible" << endl;
}