這道題數據太弱。。。。

我的方法明顯有BUG。。。

謝謝大家提醒！！！

动态规划的初始值一定要注意啊，

本题由于没赋 -maxlongint 调了N长时间

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我无语 第一次交错程序了。以前写的错的文件名叫1037 又写了个新的叫1037t 结果把旧的1037交上去得了10分= =~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用了floodfill，定义了一个2000*2000然后填表。时间效率几近裸搜但还是凑合着1A

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案正确... 556ms …………！！！

├ 测试数据 10：答案正确... 728ms …………！！！

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

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

居然有要输出Impossible

没看到-.-

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

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

冏。。。

危险啊

/*

F [i][j] 表示前i 个水晶分成两堆, 差距为j 时较矮那个的最大高度 (另一种是:表示较高那个的最大高度,状态转移过程有点区别)

F [j] 不放入第i块

F [j+A [i]] +A [i] 将第i块放在较矮的那堆,

F [j-A[i]] 将第i块放在较高的那堆

j >= A [i] 时,

F [i][j] = Max { F [j], F [j+A [i]] +A [i], F [j-A[i]] }

j < A [i] 时, 放在较矮堆照常, 放在较大堆就不可能了, 一种可能是放在较矮堆, 然后较矮堆成为较大堆

F [i][j] = Max { F [j], F [j+A [i]] +A [i], F [A [i]-j]+A [i]-j }

*/

void Work ()

{

int i, j ;

for (i = 0 ; i

靠!!!!

又是大小写!!!!

居然是Impossible!!!

写成impossible 了!!!

哇~~~~~~~~

555~~~~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

• 极为朴素的dp
  

var

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

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

i,j,m,n:integer;

function max(i,j:integer):integer;

begin

if i>j then exit(i) else exit(j);

end;

begin

readln(n);

for i:=1 to n do

begin

read(h[i]);

inc(m,h[i]);

end;

fillchar(f,sizeof(f),188);

f[0,0]:=0;

for i:=1 to n do

for j:=0 to m do

f:=max(f,max(f+h[i],f+ord(j

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

2维背包加了一点小优化.

晕倒impossible居然打成imposiible- -了....

阶段（I）：水晶数

状态（I，J）：前I个水晶差为J的最大高度

决策：Max{F 不选当前水晶

F[I-1，J+V] 将当前水晶加入矮城堡

J>=0 F[I-1，J-V]+V 将当前水晶加入高城堡

J

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

普通判定性背包会超时.

慢死了...

极为朴素的dp,加了点优化,滚动数组还是过了...

f=f or f or f;

前I个水晶能够达到左J右K的塔...

用F0保存上次的,F1保存这次的,DP一次后F0:=F1;

如何输出就不说了吧..

P.S. 用两塔差正解秒杀的大牛们不要BS我弱弱的方法...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Var

i,n,j,k:integer;

a,h:array[0..100] of integer;

f0,f1:array[-1000..1000,-1000..1000] of boolean;

Begin

readln(n);

for i:=1 to n do begin

read(a[i]);

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

if h[i]>=1000 then h[i]:=1000;

end;

f0[0,0]:=true;

for i:=1 to n do begin

for j:=0 to h[i] do

for k:=0 to h[i] do

if f0[j-a[i],k] or f0[j,k-a[i]] or f0[j,k] then

f1[j,k]:=true;

f0:=f1;

end;

for j:=h[n] downto 1 do

if f1[j,j] then begin

writeln(j);

halt;

end;

writeln('Impossible');

End.

nan

编译通过...

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

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

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

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

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

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

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

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

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

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

#include

using namespace std;

int main()

{

int a[101],dp[101][2001],i,j,n,sum;

cin>>n;

sum=0;

for(i=1;i>a[i];

sum+=a[i];

}

for(i=0;i

普通背包，把所有水晶块垒到一个塔上，然后找

for i:=maxn*maxh downto 1 do

if f[i]=f[i div 2]=1 then write break

即可

PS:这是一题菜鸟们的水题和大牛们的难题

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

var f:array[0..101,0..2001] of longint;

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

i,j,n,x:longint;

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

begin

if a>b then

max:=a

else

max:=b;

end;

begin

readln(n);

x:=0;

for i:=1 to n do

begin

read(a[i]);

inc(x,a[i]);

end;

for i:=0 to n do

for j:=0 to x do

f:=-maxlongint;

f[0,0]:=0;

for i:=1 to n do

for j:=X downto 0 do

begin

if j>=a[i] then

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

else

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

end;

if f[n,0]=0 then

writeln('Impossible')

else

writeln(f[n,0]);

end.