题解 - Vijos

0

qianpeter LV 8 @ 2009-11-01 11:49:49

program p1104;

var

i,j,k,t1,m,p:integer;

t,w:array[0..1011] of integer;

f:array[0..1011,0..1011] of integer;

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

var iii:integer;

begin

if x>y then max:=x

else max:=y;

end;

begin

readln(t1,m);

for i:=1 to m do

begin

readln(t[i],w[i]);

end;

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

for i:=1 to m do

for j:=1 to t1 do

begin

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

else f:=f;

end;

writeln(f[m,t1]);

end.

今天上午心情好，本想刷一水提助兴。

没想到这一水题，交了我3次……………………………………

好了，贴程序，积人品，供大牛鄙视

0

nightelfel LV 8 @ 2009-10-30 12:20:00

var c,w:array[0..101] of int64;

t:int64;

f:array[0..101,0..1002] of int64;

i,j,l,m,n:longint;

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

begin

if a>=b then max:=a else max:=b;

end;

function search(a,b:int64):int64;

var ans:int64;

begin

if f[a,b]n then begin search:=0;exit;end;

ans:=search(a+1,b);

if b-c[a]>=0 then

begin

ans:=max(ans,search(a+1,b-c[a])+w[a]);

end;

f[a,b]:=ans;search:=ans;

end else begin search:=f[a,b];exit;end;

end;

begin

read(t);

read(n);

for i:=1 to n do

read(c[i],w[i]);

fillchar(f,sizeof(f),255);

writeln(search(1,t));

end.

0

jiayu888 LV 8 @ 2009-10-28 00:34:09

加油

var

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

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

i,j,n,m:longint;

begin

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

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

readln(n,m);

for i:=1 to m do

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

for i:=1 to m do

for j:=n downto 1 do

if j>=t[i] then

begin

if f[j-t[i],i-1]+a[i]>f[j,i-1] then

f[j,i]:=f[j-t[i],i-1]+a[i]

else f[j,i]:=f[j,i-1];

end

else f[j,i]:=f[j,i-1];

writeln(f[n,m]);

end.

0

xgzhangs LV 8 @ 2009-10-27 22:40:05

第一次写DP，虽然复杂了点，但是动归思想很明显。。

#include

int time[101],vualue[101];

int path[1001][101]={0};

int t,m;

void init()

{

int i,j;

scanf("%d%d",&t,&m);

for(i=1;i

0

ededed LV 4 @ 2009-10-25 15:58:16

program noname02;

var t,m,i,j:longint;

a,b,f:array[1..1000]of longint;

begin

read(t,m);

for i:=1 to m do

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

for i:=1 to m do

for j:=t downto a[i] do

if f[j-a[i]]+b[i]>f[j]

then f[j]:=f[j-a[i]]+b[i];

write(f[t]);

end.

0

wangdengzhao LV 5 @ 2009-10-25 15:52:52

program lx1;

var t,m,i,j:longint;

a,b,f:array[0..1000]of longint;

begin

read(t,m);

for i:=1 to m do

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

for i:=1 to m do

for j:=t downto a[i] do

if f[j-a[i]]+b[i]>f[j]

then f[j]:=f[j-a[i]]+b[i];

write(f[t]);

end.

0

baoyingxu LV 7 @ 2009-10-13 12:38:50

Program beibao(input,output);

Var

i,j:longint;

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

v,w:array[1..1000] of longint;

t,m:longint;

Begin

readln(t,m);

for i:=1 to m do readln(w[i],v[i]);

for i:=1 to m do f:=0;

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

for i:=1 to m do

for j:=1 to t do

begin

if j>=w[i] then

if f>f+v[i] then f:=f

else f:=f+v[i]

else f:=f;

end;

writeln(f[m,t]);

End.

0

andy20333 LV 7 @ 2009-10-11 14:26:24

不知为何01背包的难度是2……

0

chaizheng LV 8 @ 2009-10-11 13:53:59

program pqqqqqqqqq;

var a,t,w:array[1..100]of integer;

i,j,k,d,t:integer;

begin

ASSIGN(INPUT,'CY.IN');

ASSIGN(OUTPUT,'CY.OUT');

RESET(INPUT);

REWRITE(OUTPUT);

{function ja(r,t:integer):integer;

begin

if r>=t then ja:=r;

if r=a[j-c[i]]+w[i] then a[i]:=a[j]

else a[i]:=a[j-c[i]]+w[i];

end;

{a[i]:=ja(a[j],a[j-c[i]]+w[i]);}

writeln(a[i]);

CLOSE(INPUT);

CLOSE(OUTPUT);

end.

先存在这里谁让我没U盘呢

0

gallenvara LV 7 @ 2009-10-04 22:31: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

lgxcgd LV 10 @ 2009-09-18 17:26:39

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

0

zhangyq987 LV 8 @ 2009-09-12 23:03:27

var

t,m,i,j,k,p:longint;

f,tt,w:packed array[0..1000]of longint;

begin

readln(t,m);f[0]:=0;p:=0;

for i:=1 to m do readln(tt[i],w[i]);

for i:=1 to m do

for j:=t downto tt[i] do

if f[j-tt[i]]+w[i]>f[j] then

begin

f[j]:=f[j-tt[i]]+w[i];

if f[j]>p then p:=f[j];

end;

write(p);

end.

普及组就是简单啊

0

wert1258 LV 8 @ 2009-09-09 19:49:09

那个牛帮帮这个为什么过不了？、

program p1104;

var t,m,i,j:integer;

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

f:array[1..1000,1..100] of integer;

begin

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

read(t,m);

for i:=1 to m do

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

for j:=1 to m do

for i:=1 to t do

if ((f[i-a[j],j-1]+b[j])>f) and (i>a[j])

then f:=f[i-a[j],j-1]+b[j] else f:=f;

writeln(f[t,m]);

end.

只有70？？

0

芒果木瓜榴莲 LV 9 @ 2009-09-07 21:27:39

编译通过...

├ 测试数据 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='p1104';

var

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

t,w:array[1..100]of longint;

i,j,k,m,n,tt: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(tt,m);

for i:=1 to m do

readln(t[i],w[i]);

for i:=1 to m do

for j:=0 to tt do

begin

f:=f;

if j>=t[i]then

f:=max(f,f+w[i]);

end;

writeln(f[m,tt]);

close(input);close(output);

end.

noip2005,日照。

普及组考试的前一天晚上微机老师让我背过01背包，说很有可能考。

我硬是没有背，因为我认为不可能考。

后悔啊……现在我都高二了，想起来还后悔

0

max-wzh LV 7 @ 2009-09-06 09:53:42

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program fsf;

var t,m,i,j:integer;

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

g:array[0..1000,0..1000] of integer;

begin

readln(t,m);

for i:=1 to m do readln(a[i],b[i]);

for i:=1 to 1000 do

for j:=1 to 1000 do g:=0;

for i:=1 to m do

for j:=1 to t do

if (j>=a[i])and(g+b[i]>g) then

g:=g+b[i] else g:=g;

write(g[m,t]);

end.

Flag 　　 Accepted

题号　　P1104

类型(?) 　　动态规划

通过　　6640人

提交　　15269次

通过率　　43%

难度　　2

提交讨论题解

0

yulingtai01 LV 9 @ 2009-08-29 19:34:56

明显的01背包问题

很简单的说

0

iphone3gs LV 8 @ 2009-08-26 12:42:21

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1104;

var p,tm:array[1..100] of integer;

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

i,j,t,m:integer;

begin

readln(t,m);

for i:=1 to m do readln(tm[i],p[i]);

for i:=1 to m do

for j:=t downto 1 do begin

if (j>=tm[i]) and (a[j]

0

tyc1993322 LV 7 @ 2009-08-19 16:35:50

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program ttt;

var i,m,n,x:longint;

f:array[0..100000] of integer;

w,c:array[0..2000] of longint;

begin

readln(m,n);

for i:=1 to n do

readln(w[i],c[i]);

for i:=1 to n do

for x:= m downto w[i] do

if f[x-w[i]]+c[i]>f[y] then f[x]:=f[x-w[i]]+c[i];

writeln(f[m]);

end.

0

姜逸伦 LV 7 @ 2009-08-18 14:15:06

#include

using namespace std;

int main()

{int a[100],c[100],f[1000];

long i,n,m,j;

cin >>m>>n;

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

for (i=0;i

0

602548825 LV 7 @ 2009-08-17 15:47:04

#include

using namespace std;

int main(){

int time=0,num=0,mtime[1001]={},mmoney[101]={},f[10001]={};

cin>>time;//采药时间

cin>>num;//草药的数目

for(int i=1;i>mtime[i]>>mmoney[i];//分别表示采摘某株草药的时间和这株草药的价值。

}

for(int i=1;i=mtime[i];j--){//从最后时间开始列举

if(f[j-mtime[i]]/*没有采药的时间的最大价值*/+mmoney[i]/*当前草药价值*/>f[j]/*采药后当前时间的最大价值*/){

f[j]=f[j-mtime[i]]+mmoney[i];//记当前时间最大价值为没有采药的时间的最大价值+当前草药价值

}

}

}

cout

题解

301 条题解

采药

信息

状态

开发

支持

题解

301 条题解

采药

信息

状态

开发

支持

还没有账户？

登录