不分高矮貌似比较慢

状态多了一倍

100 有效耗时：1322ms

高矮塔都是塔，何必强分高矮......

鲁迅先生说过:面前有两个东西，一个是塔，另一个还是塔。

var i,j,m,n,k,l,p:longint;

sum:longint;

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

begin

readln(n);

fillchar(f,sizeof(f),0);

sum:=0;

f[0,0]:=true;

for i:=1 to n do

begin

read(k);

for j:=sum downto 0 do

for l:=sum downto 0 do

if f[j,l] then

begin

f[j+k,l]:=true;

f[j,l+k]:=true;

end;

inc(sum,k)

end;

for i:=sum downto 0 do

if f then break;

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

end.

0 ms--

不错的背包

很有思维含量

var

f:array[0..110,0..2100]of longint;

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

n,m,i,j:longint;

function max(a,b:integer):integer;

begin

if a>b then exit(a)

else exit(b);

end;

begin

readln(n);

for i:=1 to n do

begin

read(a[i]);

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

end;

fillchar(f,sizeof(f),128); f[0,0]:=0;

for i:=1 to n do

for j:=0 to sum[i] do

if j>=a[i] then f:=max(f,max(f,f+a[i]))

else f:=max(f,max(f,f+j));

if f[n,0]>0 then write(f[n,0])

else write('Impossible');

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program yzh;

var

s,a:array[0..200] of longint;

f:array[0..200,0..2100] of longint;

i,j,n:integer; max:longint;

begin

read(n);

for i:=1 to n do read(a[i]);

s[0]:=0;

for i:=1 to n do s[i]:=s+a[i];

fillchar(f,sizeof(f),0);

f[1,a[1]]:=a[1];

for i:=2 to n do

for j:=0 to s[i] do

begin

max:=0;

if f>max then max:=f;

if f>max then max:=f;

if (j>=a[i]) and ((f>0) or (j-a[i]=0)) and (f+a[i]>max) then max:=f+a[i];

if (a[i]>=j) and ((f>0) or (a[i]-j=0)) and (f+j>max) then max:=f+j;

f:=max;

end;

if f[n,0]=0 then writeln('Impossible') else writeln(f[n,0]);

end.

很疑惑，不知哪位牛给我解释一下。

这道题明明是01背包，为什么很多题解中这样的循环也能过？

for i:=1 to n do

for j:=0 to sum do

......

不是应该是

for i:=1 to n do

for j:=sum downto 0 do

......

吗？？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1037;

var

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

f:array[0..130,0..2300] of longint;

i,j,n:longint;

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

begin

if a0 then

writeln(f[n,0])

else

writeln('Impossible');

end.

程序写完了，还不知道为什么要这样定义f，还有$F0什么东东，只有动态方程是知道f定义后自己的写的。

已经超出我的理解范围了

杯具啊 交了十几次才AC

原来想用装箱的 结果90分

我就奇怪了

后来发现

看错了 还以为不超过200......

一开始数组开小了 都216

后来初始化没弄好..

惨痛的教训

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

好题解！

我补充点……（写得有点乱，应该可以理解……）

f 表示不放第i块水晶;

f 表示第i块水晶放到了较矮的那个塔上，而且矮塔仍然为矮塔，填补了高度差；

因为水晶放在矮塔上，且当前的差距刚好缩短为j。显然原先差距大，所以f由f推得，差距缩短了h[i]，变为j。矮塔仍然为矮塔！

当 j>=h[i] 时:

f+h[i] 表示第i块水晶放到了较高的塔上，增加了高度差；

因为水晶放在高塔上，差距变大了，所以f由f推得。又因为f表示原先的高塔高度，而水晶放在高塔上，所以当前高塔高度还要加上增加的高度（即h[i]）

当 h[i]>j 时:

f+j 表示第i块水晶放到了较矮的那个塔上，但是矮塔变成了高塔；

这点难理解。

先看上一点的式子f+h[i]，当h[i]>j时，得出的差距是负的，即

原来的高塔成了矮塔，原来的矮塔成了高塔。

所以f的值等于原来矮塔的高度 + 增加的高度。虽然我们不知道原来矮塔的高度，但可以由原来高塔的高度得出。

当前差值j = 当前高塔高度（即原先矮塔高度 + 增加的高度h） - 当前矮塔高度（即原先高塔高度）

= （（原先高塔高度a - 原先差值x）+ 增加的高度h）- 原先高塔高度a

= 增加的高度h - 原先差值x

所以 原先差值x = 增加的高度h - 当前差值j（即x=h-j）

由于当前 增加的高度h 和 当前差值j 已知，所以可以求得 原先差值x。

而已知 原先差值x 又可得到 原先高塔高度a（即f）

所以

当前的高塔高度（即f）= 原先高塔高度a（即f）- 原先差值x + 增加的高度h

= 原先高塔高度a（即f）+ 当前差值j

所以f=f+j

初始要把f设成小于0的数

然后方程如下

f[i][j]表示前i个水晶构成的2塔差距为j时较高塔的最大高度

if(j>=a[i])

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

else

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

最后输出f[n][0]即可

我想哭。。55555555~~~~~

因为初始f[i][j] = -maxint时，偷了一下懒，把第一行忽略了。。。。。

导致wa了N次。。。。。。。。。。。。。。。。。。。。。。

题解 http://254117343.blog.163.com/

这个题很神奇，也很有创意。它与背包有些不同，却又基于背包，一般的菜鸟（比如我）就想不出来。它的转移方程也是分类讨论，对于普及组有些难度。

总之，先背过再说

我是大傻我半凹我还喜欢XXX

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

const filename='p1037';

var

n,t,i,j,sum:longint;

a:array[0..100]of longint;

f:array[0..100,0..2000]of longint;

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

begin if x>y then exit(x);exit(y);end;

begin

assign(input,filename+'.in');reset(input);

assign(output,filename+'.out');rewrite(output);

readln(n);sum:=0;

for i:=1 to n do

begin

read(a[i]);

sum:=sum+a[i];

end;

filldword(f,sizeof(f)shr 2,-maxlongint);

f[0,0]:=0;

for i:=1 to n do

for j:=0 to sum do

if a[i]0 then writeln(f[n,0])else writeln('Impossible');

close(input);close(output);

end.

for i:=0 to 100 do for j:=0 to 2000 do f:=-100000;

居然打成

for i:=1 to 100 do for j:=1 to 2000 do f:=-100000;

连错三遍……通过率……

切记切记

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

动归。

#include"stdio.h"

long f[2][200001];

int main()

{ long i,j,k,m,n;

long s[101]={0},a[101];

memset(f,0,sizeof(f));

scanf("%ld",&n);

for(i=1;i=0&&m=j-a[i])

m=f[j-a[i]]+a[i];

if(j-a[i]0)

{ if(m

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

慢啊~~~~

program p1037;

var

s,a:array[0..200] of longint;

f:array[0..200,0..2100] of longint;

i,j,n:integer; max:longint;

begin

read(n);

for i:=1 to n do read(a[i]);

s[0]:=0;

for i:=1 to n do s[i]:=s+a[i];

fillchar(f,sizeof(f),0);

f[1,a[1]]:=a[1];

for i:=2 to n do

for j:=0 to s[i] do

begin

max:=0;

if f>max then max:=f;

if f>max then max:=f;

if (j>=a[i]) and *|((f>0) or (j-a[i]=0))*| and (f+a[i]>max) then max:=f+a[i];

if (a[i]>=j) and *|((f>0) or (a[i]-j=0))*| and (f+j>max) then max:=f+j;

f:=max;

end;

if f[n,0]=0 then writeln('Impossible') else writeln(f[n,0]);

end.

DP方程比较容易写出来，但是边界条件要细心的处理/星号中的判断语句

*|((f>0) or (j-a[i]=0))*| ，*|((f>0) or (a[i]-j=0))*|

非常重要，因为对于任意的i>=1,j>=1，如果f=0则代表这种状态不存在，但是最重要的是当j=0时，这种不存在是有实际意义的，所以我写了两条判断语句。就是因为这个原因，本人WA了N次，

~~~~~~~~~~~~终于AC了！！！！！！！！！！

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

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

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

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

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

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

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

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

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

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

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

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

水题！背包优化一下才169~~~~~~~~~~