暴力

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

广东实验中学观光团到此一游

很险就要超时了，不知牛们怎么优化，竟然能秒杀，望能不吝指教，多谢……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

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

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

i,j,k,l,n,num,num1:longint;

b:boolean;

begin

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

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

readln(n);

num1:=maxint;

for i:=1 to n do

begin

j:=0;

num:=0;

a:=0;

f:=1;

while a-1 do

begin

inc(j);

read(a);

num:=num+a;

end;

a:=0;

dec(j);

num:=num+1;

a:=num;

if num=a) and (f[i,l-a]=1) then f:=1;

end;

for i:=num1 downto 0 do

begin

b:=true;

for j:=1 to n do

if f[j,i]=0 then begin b:=false; break; end;

if b then begin writeln(i); halt; end;

end;

writeln('0');

end.

writeln(k);

end.

谁给我个详细的题解??

#include

int main()

{

int a,b; scanf( 0;

}

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

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

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

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

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

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

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

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

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

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

ac两次，速度还是非常慢。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

何以秒杀！唯有puppy！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

很稀有的发一个C++程序哈：

#include

using namespace std;

bool f[20000];

long g[20000];

long x,h,maxl,k,i,j,n;

int main()

{

cin>>n;

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

f[0]=true;

for(k=1;k>x;

while(x!=-1)

{

h+=x;

for(i=h;i>=0;--i)

{

if(f[i] && !f)

{

f=true;

++g;

}

}

cin>>x;

}

for(i=h;i>=1;--i) f[i]=false;

if(h>maxl) maxl=h;

}

for(i=maxl;i>=1;--i)

{

if(g[i]==n)

{

cout

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

稍稍改进 还是没能AC

我弱弱的问

for i:=min downto 1 do

　　if g[i]=n then

　　 begin writeln(i);halt;end;

writeln(0);

这个改成

for i:=min downto 0 do

　　if g[i]=n then

　　 begin writeln(i);halt;end;

怎么有一个超时啊

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

比较朴素，没啥优化……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1059;

var

f:array[0..20000] of boolean;

g:array[0..20000] of integer;

s,p,n,i,j,min:integer;

begin

read(n);

fillchar(g,sizeof(g),0);

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

min:=32145;

for i:=1 to n do

begin

s:=0; f[0]:=true;

read(p);

while p-1 do

begin

///// for j:=s downto 0 do////十分重要，如果将downto改成to那么就错了

if f[j] and (not(f[j+p])) then begin f[j+p]:=true; inc(g[j+p]); end;

s:=s+p; read(p);

end;

if s

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var f,g:array[0..20000] of integer;

i,j,n,s,h,min:longint;

begin

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

fillchar(g,sizeof(g),0);

readln(n);f[0]:=1;

min:=maxlongint;

for i:=1 to n do

begin

h:=0;read(s);

while s-1 do

begin

for j:=h downto 0 do

if (f[j]=1) and (f[j+s]=0) then

begin f[j+s]:=1;inc(g[j+s]);end;

inc(h,s);read(s);

end;

for j:=1 to h do f[j]:=0;

if h

100个背包...

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

求解秒杀算法

用背包做

...不一定都从底部抽，N次20分

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

终于过了，好险啊………………

奇迹。。。。。。。。。。。。。。。。。。。

一个菜鸟居然秒杀了 积木城堡。。。。。。- -||（或许是我RP爆发了。。）

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program jimu;

var a:array[1..10000000]of longint;

f,c:array[1..10001]of longint;

n,q,i,x,k,k1:longint;

begin

read(n);

for q:=1 to n do

begin

k:=0;

read(x);

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

while x-1 do

begin

k1:=k;

for i:=1 to k do

if (f[a[i]+x]=0) then

begin

f[a[i]+x]:=1;

inc(k1);

a[k1]:=a[i]+x;

end;

if f[x]=0 then

begin

inc(k1);

a[k1]:=x;

f[x]:=1;

end;

k:=k1;

read(x);

end;

for i:=1 to k do

inc(c[a[i]]);

end;

for i:=10000 downto 1 do

if c[i]=n then

begin

writeln(i);

exit;

end;

writeln(0);

end.

直接100个背包会超时

有一个小窍门是

定义一个 min 记录最矮的塔是多高

每一个背包只要做到f[min]就行了