Orz秒杀巨神，三维水过无脑dp。。

测试数据 #0: Accepted, time = 0 ms, mem = 1372 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1368 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1372 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1376 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1372 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1376 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1372 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1372 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1376 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1372 KiB, score = 10
Accepted, time = 0 ms, mem = 1376 KiB, score = 100
题解+标程

背包做的，不过没有想到诸位的做法。我的做法是：先求容量为2*H的背包，再在2*H的背包里求容量为H的背包，大概是O(N*(sum(Hi))

/*

 * vijos-1037

 * mike-w

 * 2012-11-03

 * **|\**|\**|\**|\**|\**|\**|\**|\**|\**|\**|

 */

#include

#include

#include

#define MAXN 111

#define MAXH 2222

int opt[MAXH];

int h[MAXN];

int N, T;

int comp(const void *e1, const void *e2)

{

return *((int*)e1) - *((int*)e2);

}

int check(int hh)

{

int prv[MAXH][2];

int hh2=2*hh;

int i, j, t;

/*

* prv[i][0]: previous height 

* prv[i][1]: last added tower

*/

for(i=0; i=h[t]; j--)

if(opt[j-h[t]])

opt[j]=1;

}

return opt[hh]?1:0;

}

int main(void)

{

int i, ans=0;

scanf("%d", &N);

for(i=0; i=1; i--)

if(check(i))

ans=i, i=0;

if(!ans)

puts("Impossible");

else

printf("%d\n", ans);

return 0;

}

无脑暴力　sum *sum *ｎ
#include <cstdio>

using namespace std;
bool inq[N][N];
int u,n,sum,x;

int main() {

scanf("%d",&n);
inq[0][0] = 1;
for(int k = 0;k < n;k++) {
scanf("%d",&x);
for(int i = sum;i > -1;i--)
for(int j = i;j > -1;j--)
if(inq[i][j]) {
if(j+x <= i) inq[i][j+x] = 1;
else inq[j+x][i] = 1;
inq[i+x][j] = 1;
}

sum += x;
}
for(int i = sum;i > 0;i--) if(inq[i][i]) { printf("%d\n",i); return 0;}
puts("Impossible");
return 0;
}

/*
*/