汗....一道水DP....可是时间太难看...

var

n:integer;

f:array[0..1000,0..1000]of boolean;

a:array[1..200]of longint;

tot:longint;

k,i,j:longint;

begin

readln(n);

for i:=1 to n do

begin

read(a[i]);

tot:=tot+a[i];

end;

tot:=tot div 2;

f[0,0]:=true;

for k:=1 to n do

for i:=tot downto 0 do

for j:=tot downto 0 do

if not(f) then

if(i>=a[k])and(f[i-a[k],j]) then f:=true

else

if(j>=a[k])and(f[i,j-a[k]]) then f:=true;

for i:=tot downto 1 do

if f then

begin

writeln(i);

halt;

end;

writeln('mposible');

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 134ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 166ms

├ 测试数据 07：答案正确... 353ms

├ 测试数据 08：答案正确... 478ms

├ 测试数据 09：答案正确... 619ms

├ 测试数据 10：答案正确... 681ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2431ms

var

n,i,j,k,h,tot:integer;

f:array[0..2000,0..2000] of boolean;

a:array[1..100] of integer;

begin

readln(n);

fillchar(f,sizeof(f),false);

for i:=1 to n do

begin

read(a[i]);

h:=h+a[i];

tot:=h div 2;

end;

f[0,0]:=true;

for k:=1 to n do

begin

for i:=tot downto 0 do

for j:=tot downto 0 do

if not f then

if (i>=a[k]) and (f[i-a[k],j])

then f:=true

else if (j>=a[k]) and (f[i,j-a[k]])

then f:=true;

end;

for i:=h downto 1 do

if f then

begin

writeln(i);

halt;

end;

writeln('Impossible');

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：34ms

数组要开大

RT

whyvine的解题报告：

http://blog.sina.com.cn/s/blog_618b6ea70100egkx.html

应该是比下面所有人说的都详细了，绝对能明白

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

郁闷，wa了一次。初始化和赋初值一定不能搞反啊

终于过了，关键在动态转移方程时，要保证要往上累加的值不能等于零，因为要是总高度等于零，又何来第一堆比第二堆高几了，是吧，这也是他们把初值附为-maxlongint的原因了！

fillchar(f,sizeof(f),$F0);这个是怎么意思?``

程序20行，但是交了3次

分享错因：

1、在调试时加数组初始值设的太大了（-100） 20分

2、改动了初始值（-1000000），但是没有考虑不放当前块的情况，50分

3、ac

思考的出发点是放上物块（或不放）后差值的变化

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

虽然不知道为什么那么多人要把记录贴上来，不过既然那么多人这么做了就跟着做了。

看了题解才晓得该怎么做的，滚动数组很省~~动态方程是之前没见过的~~又学到了一点。

http://hi.baidu.com/%CB%D5%CC%DAsauterne/blog

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

program p_1037;

var f:array[0..200,0..2000] of integer;

a,n,i,j,k,l,m,ans:integer;

function max(x,y:integer):integer;

begin

if x>y then

exit(x);

exit(y);

end;

begin

readln(n);

for i:=1 to n do

begin

read(a);

inc(m,a);

f:=max(f,f+a);

for j:=1 to m do

if f>0 then

begin

f:=max(f,max(f+a,f));

if aans then

ans:=f;

end;

if ans>0 then

writeln(ans)

else

writeln('Impossible');

end.

为什么只过了八个点？

终于AC了TT

无奈啊~

program mm;

var

a,sum:array[0..103] of longint;

f:array[0..103,0..2030] of longint;

i,j,k,l,m,n,x,y,z:longint;

function max(a,b,c:longint):longint;

begin

max:=a;

if b>max then max:=b;

if c>max then max:=c;

end;

begin

fillchar(a,sizeof(a),0);

fillchar(f,sizeof(f),$F0);

readln(n);

for i:=1 to n do

read(a[i]);

f[0,0]:=0;

for i:=1 to n do

sum[i]:=sum+a[i];

for i:=1 to n do

for j:=0 to sum[n] do begin

if a[i]0

then writeln(f[n,0])

else writeln('Impossible');

end.

秒杀

用F表示前I个点，J的高度差所能达到的最高高度，2种情况

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var

i,j,k,s,n,m:longint;

f:array[0..2002,0..2002] of longint;

a:array[0..1000] of integer;

function max(a,b,c:longint):longint;

begin

max:=a;

if b>max then max:=b;

if c>max then max:=c;

end;

begin

readln(n);

s:=0;

for i:=1 to n do begin

read(a[i]);

inc(s,a[i]);

end;

for i:=1 to n-1 do

for j:=1 to n-i do

if a[i]>a then

begin

a[0]:=a[i];

a[i]:=a;

a:=a[0];

end;

fillchar(f,sizeof(f),$f0);

s:=s div 2+1;

f[0,0]:=0;

for i:=1 to n do

for j:=s downto 0 do

if a[i]>=j then

f:=max(f,f+a[i]-j,f+a[i])

else

f:=max(f,f,f+a[i]);

k:=0;

for i:=1 to n do

if f>k then

k:=f;

if k0 then writeln(k)

else writeln('Impossible');

end.

program p1037;

var

n,i,j,k,m:word;

a:array[1..100]of word;

f:array[0..2000,0..2000]of boolean;

begin

readln(n);

for i:=1 to n do

read(a[i]);

readln;

for k:=1 to n do

begin

for i:=m downto 0 do

for j:=m-i downto 0 do

if fthen

begin

f[i,j+a[k]]:=true;

f[i+a[k],j]:=true;

end;

f[a[k],0]:=true;

f[0,a[k]]:=true;

inc(m,a[k]);

end;

for i:=m downto 0 do

if f then

begin

writeln(i);

break;

end;

if i=0 then writeln('Impossible');

end.

我的做法奇慢无比，不过比较朴素。dp表示两个塔的高度分别为i和j是否可行，初始dp[0,0]=true。然后有限背包。注意常数优化，最慢的点0.5x秒出解。

两种做法：

1.开boolean数组做，类似01背包，就是有多少种可能就开个boolean;

2.开longint数组做，有四种g情况(f 表示用前i个搭成高度差为j的双塔中高塔的高度 1,a[i]不用 2.a[i]放到高的塔上 3.a[i]放到低的塔上，可能低塔还是低塔，可能低塔就变成高塔了),方程各位大牛都写的很好，实在不行自己画图也能出来。这种做法要注意：初始化的时候f:=-1000,赋成0的话会有几种不可能的情况出现，使你的答案变大。

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

f[x,y]表示前x个水晶差为y矮塔的最高高度

感谢底楼大牛提供这么奇特的思路,排序都不用了

f //当你添地i块水晶时

=max{ f, //不用它

f, //放在高的上面

f+h[i], //放在低的上面,如果j