program p1037;
var
n,sum,a,b:longint;
h:array[1..100]of integer;
f:array[0..100,0..2000]of integer;
function max(a,b,c:integer):integer;
begin
if (a>b)and(a>c) then exit(a)
else if b>c then exit(b)
else exit(c);
end;
begin
readln(n);
sum:=0;
for a:=1 to n do
begin
read(h[a]);
inc(sum,h[a]);
end;
readln;
for a:=1 to sum do
f[0,a]:=0;
for a:=1 to n do
for b:=0 to sum do
if b>=h[a] then f[a,b]:=max(f[a-1,b],f[a-1,b+h[a]],f[a-1,b-h[a]]+h[a])
else f[a,b]:=max(f[a-1,b],f[a-1,b+h[a]],f[a-1,h[a]-b]+b);
if f[n,0]>0 then writeln(f[n,0])
else writeln('Impossible');
end.
3 条评论
-
1390321418 LV 8 @ 2016-01-27 16:17:04
数据水爆
编译成功Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(6,28) Warning: Variable "t" does not seem to be initialized
Linking foo.exe
7 lines compiled, 0.0 sec, 27344 bytes code, 1268 bytes data
1 warning(s) issued测试数据 #0: Accepted, time = 0 ms, mem = 816 KiB, score = 10
测试数据 #1: WrongAnswer, time = 0 ms, mem = 816 KiB, score = 0
测试数据 #2: WrongAnswer, time = 0 ms, mem = 812 KiB, score = 0
测试数据 #3: WrongAnswer, time = 15 ms, mem = 812 KiB, score = 0
测试数据 #4: WrongAnswer, time = 0 ms, mem = 812 KiB, score = 0
测试数据 #5: WrongAnswer, time = 0 ms, mem = 812 KiB, score = 0
测试数据 #6: WrongAnswer, time = 0 ms, mem = 812 KiB, score = 0
测试数据 #7: Accepted, time = 0 ms, mem = 812 KiB, score = 10
测试数据 #8: WrongAnswer, time = 0 ms, mem = 816 KiB, score = 0
测试数据 #9: WrongAnswer, time = 0 ms, mem = 816 KiB, score = 0
WrongAnswer, time = 15 ms, mem = 816 KiB, score = 20
代码var a: array[1..100] of Longint;
i,n,t: Longint;
begin
read(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do inc(t,a[i]);
write(t div 2);
end. -
@ 2014-07-17 12:55:06
编译成功
Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
Copyright (c) 1993-2012 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(2,11) Note: Local variable "ans" not used
Linking foo.exe
40 lines compiled, 0.3 sec , 28576 bytes code, 1644 bytes data
1 note(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 4528 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 4524 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 4528 KiB, score = 10
测试数据 #3: Accepted, time = 140 ms, mem = 4524 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 4532 KiB, score = 10
测试数据 #5: Accepted, time = 156 ms, mem = 4528 KiB, score = 10
测试数据 #6: Accepted, time = 234 ms, mem = 4528 KiB, score = 10
测试数据 #7: Accepted, time = 436 ms, mem = 4528 KiB, score = 10
测试数据 #8: Accepted, time = 343 ms, mem = 4528 KiB, score = 10
测试数据 #9: Accepted, time = 468 ms, mem = 4528 KiB, score = 10
Accepted, time = 1792 ms, mem = 4532 KiB, score = 100 -
@ 2014-07-17 12:54:30
var
n,i,j,k,ans,total:longint;
a:array[1..100]of longint;
f:array[0..2000,0..2000]of boolean;procedure init;
begin
readln(n); total:=0;
for i:=1 to n do
begin read(a[i]);total:=total+a[i];end;
fillchar(f,sizeof(f),false);
total:=total div 2;
end;procedure dp;
begin
f[0,0]:=true;
for i:=1 to n do
begin
for j:=total downto 0 do
begin
for k:=total downto 0 do
begin
if (a[i]<=j) and (f[j-a[i],k]) then f[j,k]:=true else
if (a[i]<=k) and (f[j,k-a[i]]) then f[j,k]:=true;
end;
end;
end;
end;procedure print;
begin
for i:=total downto 1 do
if f[i,i] then begin writeln(i);readln;readln;halt;end;
writeln('Impossible');
end;
begin
init;
dp;
print;
end.
- 1
