题解 - Vijos

0

2mc LV 10 @ 2008-10-04 21:14:48

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

噢~~~1☆纪念

0

YY_0227 LV 8 @ 2009-07-06 20:36:50

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

背包，一眼望去就知道

0

wzj LV 8 @ 2008-09-27 21:03:56

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

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

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

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

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

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

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

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

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

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

对于刚开始为什么出问题很无奈....

终于AC了！

oh，YES!

0

bochuan007 LV 3 @ 2008-09-25 22:58:07

终于A了。。。

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

for i:=1 to m do begin

readln(a,b);

for j:=t-a downto 0 do if (w[j]+b)>w[j+a] then w[j+a]:=w[j]+b;

end;

只是背包我一向用背的，没理解到的说。。。

0

woo_50 LV 9 @ 2008-09-25 21:52:28

练习一维背包中`\`

0

toutun LV 3 @ 2008-09-22 12:27:50

program p1104;

var t,m,i,j,a,b:integer;

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

begin

readln(t,m);

fillchar(w,sizeof(w),0);

for i:=1 to m do begin

readln(a,b);

for j:=t-a downto 0 do if (w[j]+b)>w[j+a] then w[j+a]:=w[j]+b;

end;

writeln(w[t]);

end.

0

月De孤独 LV 3 @ 2008-09-22 09:21:11

无聊的0/1背包别说DP了我刚看见这题时候DFS搞定的

Program Medic;

Const

Maxt = 1001;

Maxm = 101;

Type

GArr = Record

t, v: Longint;

End;

Var

G: Array [0..Maxm] Of GArr;

Opt: Array [0..Maxm,0..Maxt] Of Longint;

i, j, t, m, Ans :Longint;

Function Max (a, b: Longint): Longint;

Begin

If a > b Then Max := a Else Max := b;

End;

Procedure Find(i, j: Longint);

Begin

If (i = 0) Or (j = 0) Then Begin

Opt[i, j] := 0;

Exit;

End;

If j < G[i].t Then Begin

If Opt[i - 1, j] = -1 Then Find(i - 1, j);

Opt[i, j] := Opt[i - 1, j];

End Else Begin

If Opt[i - 1, j - G[i].t] = -1 Then Find(i - 1, j - G[i].t);

If Opt[i - 1, j] = -1 Then Find(i - 1, j);

Opt[i, j] := Max(Opt[i - 1, j - G[i].t] + G[i].v, Opt[i - 1, j]);

End;

End;

Begin

FillChar(G, SizeOf(G), 0);

FillChar(Opt, SizeOf(Opt), 255);

ReadLn(t, m);

For i:= 1 To m Do ReadLn(G[i].t, G[i].v);

Find(m, t);

Ans := Opt[m, t];

Write(Ans);

End.

0

Dracula, LV 3 @ 2008-09-18 13:01:31

。

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

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

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

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

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

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

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

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

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

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

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

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

FP里面根本就解不出来，

丢上来这样。

0

南瓜林木 LV 3 @ 2008-09-14 21:25:52

变态，居然超时~

0

傻小子V2 LV 7 @ 2008-10-20 21:15:44

好难啊！

0

佐璇 LV 4 @ 2008-09-09 16:55:09

program p1104;

var n,t,i,j,x,y:longint;

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

begin

fillchar(v,sizeof(v),0);

readln(t,n);

for i:=1 to n do

begin

read(x,y);

for j:=t downto x do

if v[j-x]+y>v[j] then v[j]:=v[j-x]+y;

end;

writeln(v[t]);

end.

可怜啊~~输入READ多了个LN就挂了两次~~

0

冬日阳光 LV 9 @ 2008-09-06 14:56:40

program p_1;

var x:array[0..1000] of longint;

i,j,t,n,t1,v:longint;

begin

readln(t,n);

for i:=1 to n do

begin

readln(t1,v);

if t1x[j] then x[j]:=x[j-t1]+v;

end;

write(x[t]);

end.

学的某牛

好崇拜

0

maddog LV 3 @ 2008-09-05 12:42:35

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一颗星纪念

0

gyg520zhy LV 3 @ 2008-09-03 19:33:09

program ads;

var

v,p:array[1..1000]of integer;

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

i,j,m,t:integer;

begin

read(t,m);

for i:=1 to m do

readln(v[i],p[i]);

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

for i:=1 to m do

for j:=1 to t do

begin

if j>=v[i] then

begin

if (a+p[i])>a then

a:=a+p[i]

else a:=a

end

else a:=a;

end;

writeln(a[m,t]);

end.

0

bowen1 LV 3 @ 2008-09-01 09:03:41

太简单了吧，，，。

郁闷，，

最弱智的DP···

0

hllyq1 LV 6 @ 2008-08-31 12:53:45

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

i和j写反了，交了N遍

0

accoropitor LV 3 @ 2008-08-27 17:56:06

正的是完全背包的做法，倒着是01背包的做法……

意义、作用不同。。

去看《背包九讲》吧。

0

lirenjue LV 10 @ 2008-08-27 17:22:00

编译通过...

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

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

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

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

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

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

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

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

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

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

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

0

wly888_1214 LV 3 @ 2008-08-27 12:15:47

哪位大牛能解释一下，为什么这题状态转移时，正着0分，倒着就AC？

很苦恼~~

0

makaida LV 8 @ 2008-08-26 20:23:37

编译通过...

├ 测试数据 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,l,m,n:integer;

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

c:array[0..1000,0..1000] of longint;

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

begin

if x>y then max:=x else max:=y;

end;

begin

readln(m,n);

for i:=1 to n do

readln(a[i],b[i]);

fillchar(c,sizeof(c),0);

for i:=1 to n do

begin

for j:=m downto 1 do

begin

if j>=a[i] then

c:=max(c,c+b[i])

else

c:=c;

end;

end;

writeln(c[n,m]);

end.

背包就背包还采药快倒了~

题解

301 条题解

采药

信息

状态

开发

支持

题解

301 条题解

采药

信息

状态

开发

支持

还没有账户？

登录