水题

Accepted 100 From 葱_头－ P1059 FPC

这道题之所以能AC 都是靠他 Vijos Dragon

要是遇到 dolphin 你就疯吧

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用DP做的。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我faint~

那些0ms的大牛是怎么做到的啊~~

燕麦

你到底过了没啊

从哪里抄的题解啊

呵呵

(*^__^*) 嘻嘻……

到底是不是动态啊

阿东VS燕麦

咋看不象是动态规划...

其实的确不是很严格的DP...

其实，看这个题目就了解，只要把每个城堡可以到达的所有高度求出，然后看哪个高度是所有城堡共有的，输出就可以，否则就是0.

本题的关键就是把每个城堡可以到达的所有高度求出，其实有很多种方法.

这里就说DP吧，可以用01背包的思想，先计算出体积和最小的的城堡，然后将其他城堡的积木放入这个minv的背包里.在这里，价值和体积都等于每个积木的体积.

然后，AC 但是这评测机vag6k不知出啥病

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：运行超时...

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

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

Unaccepted 有效得分：0 有效耗时：0ms

var

bo,hh:byte;

n,i,j:integer;

k,hhh:longint;

total,c,h:array[1..10001]of integer;

s,l:array[1..100,0..10001]of integer;

begin

j:=0;

readln(n);

for i:=1 to n do begin

while l-1 do

begin

inc(j);

read(l);

total[i]:=total[i]+l;{计算每个城堡的高度存入total}

end; readln; end;{读入}

j:=1; k:=0;

for i:=1 to n do{计算每个城堡所有可能达到的高度存入s}

while l0 do

begin

s:=total[i]-l; inc(j);

inc(k); c[k]:=s;

end;

j:=1; k:=0;

repeat{求所有城堡的公有高度并取最大值h}

inc(k);

for i:=1 to n do while s0 do if s=c[k] then inc(bo);

if bo>=n then begin inc(hh); h[hh]:=c[k]; end;

until c[k]=0;

for j:=1 to hh do

for i:=1 to hh-1 do

if h[hh]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

读入同时直接动规……很囧……vag 6k果然快于dolphin……

为什么直接找到所以城堡中每个最高高度的最小值输出?

第一遍交(Vijos Dolphin)

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：运行超时...

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

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

Unaccepted 有效得分：90 有效耗时：511ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

find:boolean;

f:array[0..100,1..10001]of boolean;

h:array[1..10000]of longint;

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

begin

readln(n);

for i:=1 to n do

f:=true;

max:=0;

for i:=1 to n do

begin

repeat

read(m);

if m=-1 then break;

inc(h[i],m);

for j:=h[i] downto m do

if f then f:=true;

until m=-1;

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

end;

find:=true;

for j:=max downto 1 do

begin

find:=true;

for I:=1 to n do

if not f then begin find:=false;break;end;

if find then begin writeln(j);exit;end;

end;

writeln(0);

end.

一样的程序第二次交就变成了

编译通过...

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

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

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

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

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

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

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

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

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

├ 测试数据 10：运行超时...

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

Unaccepted 有效得分：90 有效耗时：25ms

诡异~囧啊！

program v1059;

var h:array[1..100,0..10000]of boolean;

i,x,hm,j,min,n:longint;

t:boolean;

begin

readln(n);

fillchar(h,sizeof(h),false);

for i:=1 to n do h:=true;

min:=maxlongint;

for i:=1 to n do begin

read(x);

hm:=x;h:=true;

read(x);

while x>-1 do begin

for j:=hm downto 0 do if h then h:=true;

hm:=hm+x;

read(x);

end;

if hm0) do begin

t:=true;

for i:=1 to n do

if h=false then begin

t:=false;break;

end;

if not t then min:=min-1;

end;

writeln(min);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

谁知道最后三组是什么数据啊

就是过不了

给的结果好像是发生错误128

怪不得难度是1..

原来最朴素的方法就ok了.

DP：

1）

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

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

囧，每次用DP都那么危险啊？

2）将每个城堡的所有能达到的高度都算出来，可以用一个boolean类型数组存

3）对于每个城堡f[i]表示能达到i这个高度的城堡数，显然，ans=（max{f[i]}）的序号i，其中f[i]=n。

本打算要第2000个通过来着，但还没做出来，就有一人跑我前面了，那个第2000的，你夺人之美啊！然后编完了，但最后三个数据用我的程序是怎么都过不了，我 直接囧了！！！ 然后改变思路，所谓的改变也就是将我那个 2dp+1排序+1字符串转换 改成了 1dp！ 然后就过了 ！不过 我是第2006 ac的！ 2008也可以啊！哎!为什么？老天啊！

Flag 　　Accepted

题号 　　P1059

类型(?) 　　动态规划

通过 　　2006人

提交 　　7486次

通过率 　　27%

难度 　　1

此题绝对不是rp问题

dp不会超的

同意LV.唱响的解法

但这道题确实是dp

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

f:array[0..10000] of longint;

vi:array[0..10000] of boolean;

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

n,i,x,j,max,hm:longint;

begin

readln(n);

for i:=1 to n do

begin

fillchar(vi,sizeof(vi),0);

vi[0]:=true;max:=0;

read(x);

while x-1 do

begin

for j:=max downto 0 do

if vi[j] then vi[j+x]:=true;

max:=max+x;

read(x);

end;

for j:=0 to max do

if vi[j] then inc(f[j]);

if max>hm then hm:=max;

end;

for i:=hm downto 0 do

if f[i]=n then

begin

writeln(i);

exit;

end;

end.

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

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

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

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

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

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

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

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

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

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

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

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

注意别设错数组

program c1;

var f:array[1..100,1..10000]of boolean;

ans:array[0..10000]of longint;

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

k,i,j,d,n,m,t,max:longint;

function check(k:longint):boolean;

var i:longint;

begin

check:=true;

for i:=1 to n do

if not f then exit(false);

end;

begin

readln(n);fillchar(f,sizeof(f),false);max:=-111;

for d:=1to n do

begin

i:=0;read(t);fillword(a,sizeof(a)shr 1,0);

while t-1 do begin inc(i);a[i]:=t;read(t);end;

m:=i;ans[0]:=1;ans[1]:=0;

for i:=1 to m do

begin

k:=ans[0];

for j:=1 to ans[0] do

begin

if not f[d,ans[j]+a[i]] then

begin

inc(k);

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

if ans[k]>max then max:=ans[k];end;

end;

ans[0]:=k;

end;

end;

for i:=max downto 0 do begin

if check(i) then begin writeln(i);break;end; if i=0 then write(0);end;

end.

为什么啊啊啊啊啊！！！！！！！！！！！！！！

编译通过...

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

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

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

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

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

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

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

├ 测试数据 08：运行超时|无输出...

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

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

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

Unaccepted 有效得分：90 有效耗时：1035ms

var f:array[1..100,0..6000]of byte;

i,v,j,n,s,t,h:longint;

begin

readln(n);h:=0;

for i:=1 to n do f:=1;

for v:=1 to n do

begin

for j:=1 to 100 do

begin

read(t);

if t=-1 then break;

for i:=h downto 0 do

if f[v,i]=1 then

begin f[v,i+t]:=1;if h

I want to kill the lora temper!!!!!!!

第一次：第九个点超时

第二次：第十个点超时

第三次：第九个点超时

第四次：第九个点超时

第五次：第十个点超时

……

第N！次：AC……一个程序怎么还可以变来变去的？！！！