301 条题解
-
0
dijkstrloyd LV 7 @ 2013-10-28 23:47:03
来个短的
var
i,j,t,m,c,v:integer;
f:array[0..1000]of integer;function max(a,b:integer):integer;
begin
if a>b then exit(a) else exit(b);
end;begin
fillchar(f,sizeof(f),0);
readln(t,m);
for i:=1 to m do begin
readln(c,v);
for j:=t downto c do f[j]:=max(f[j],f[j-c]+v)
end;
writeln(f[t]);
end. -
0
ChinaLover LV 7 @ 2013-08-25 10:15:20
0秒水过，鄙视那些只贴结果的人。
这是入门级动归
01背包问题
用一维数组逆向推就可以了
附上我丑陋的程序。。。
program medcine;
var value:array[0..1200] of longint;
t,i,j,m,a,b,max:longint;
begin
readln(t,m);
for i:=1 to t do value[i]:=-1;
for i:=1 to m do
begin
readln(a,b);
for j:=t downto 0 do
if value[j]>=0 then
if value[j]+b>value[j+a] then value[j+a]:=value[j]+b;
end;
max:=-1;
for i:=t downto 0 do
if value[i]>max then max:=value[i];
writeln(max);
end. -
0
测试数据 #0: Accepted, time = 193 ms, mem = 640 KiB, score = 10
测试数据 #1: Accepted, time = 12 ms, mem = 640 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 640 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 640 KiB, score = 10
测试数据 #4: Accepted, time = 12 ms, mem = 640 KiB, score = 10
测试数据 #5: Accepted, time = 127 ms, mem = 640 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 640 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 640 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 640 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 640 KiB, score = 10
Accepted, time = 389 ms, mem = 640 KiB, score = 100
-
0
theniceboy LV 7 @ 2013-02-01 11:15:51
#include<iostream>
using namespace std;
int f[1002],c[102],w[102],n,v,i,j;
int main()
{
cin>>v>>n;
for(i=1;i<=n;++i)
cin>>c[i]>>w[i];
for(i=1;i<=n;i++)
for(j=v;j>=c[i];--j)
f[j]=max(f[j],f[j-c[i]]+w[i]);
cout<<f[v]<<endl;
return 0;
} -
0
纪念水题...
├ 测试数据 01：答案正确... (63ms, 4332KB)
├ 测试数据 02：答案正确... (0ms, 4332KB)
├ 测试数据 03：答案正确... (47ms, 4328KB)
├ 测试数据 04：答案正确... (47ms, 4332KB)
├ 测试数据 05：答案正确... (16ms, 4332KB)
├ 测试数据 06：答案正确... (0ms, 4332KB)
├ 测试数据 07：答案正确... (31ms, 4332KB)
├ 测试数据 08：答案正确... (31ms, 4332KB)
├ 测试数据 09：答案正确... (47ms, 4332KB)
├ 测试数据 10：答案正确... (47ms, 4332KB)---|---|---|---|---|---|---|---|-
Accepted / 100 / 333ms / 4332KB
二维数组不会爆，没必要优化此题 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms程序代码：
var
time,value:array[1..100] of integer;
f:array[0..1001] of integer;
t,m,i,j:integer;function max(x,y:integer):integer;
begin
if x>y then max:=x
else max:=y;
end;begin
readln(t,m);
for i:=1 to m do
readln(time[i],value[i]);
for i:=1 to m do
for j:=t downto 1 do
if j-time[i]>=0 then
f[j]:=max(f[j],f[j-time[i]]+value[i]);
write(f[t]);
end. -
0
tony970724 LV 5 @ 2010-04-10 14:30:27
01背包
水题#include
using namespace std;
int main()
{
int m,n,t[101],v[101],j,i,f[101][1001]={0};//f[i][j]
cin>>n>>m;
for(i=1;i>t[i]>>v[i];
for(i=1;if[j])
f[i][j]=f[j-t[i]]+v[i];
else
f[i][j]=f[j];}
cout -
0
小小的留个名字....
var
t,m,i,j:integer;
yt:array[1..100] of integer;
v:array[1..100] of integer;
f:array[0..1000,0..1000] of integer;
function max(a,b:integer):integer;
begin
if a>b then max:=a
else max:=b;
end;
begin
readLn(t,m);
for i:=1 to m do readLn(yt[i],v[i]);
for i:=1 to m do
for j:=1 to t do begin
if j>=yt[i] then
f:=max(f,f+v[i])
else f:=f;
end;
write(f[m,t]);
end.
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
正宗的01背包……
var
t,m,i,j:longint;
v,w:array[1..100] of longint;
f:array[0..1000] of longint;
begin
readln(t,m);
for i:=1 to m do readln(v[i],w[i]);
fillchar(f,sizeof(f),0);
for i:=1 to m do
for j:=t downto v[i] do
if f[j-v[i]]+w[i]>f[j]
then f[j]:=f[j-v[i]]+w[i];
writeln(f[t]);
end -
0
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. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
#include "stdio.h"
int time=0,num=0;
int f[1001]={0};
int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
int bag(int costime,int costvalue)
{
int i=0;
for(i=time;i>=costime;i--)
{
f[i]=max(f[i],f+costvalue);
}
}
int main()
{int i=0;
int a,b;
scanf("%d %d",&time,&num);
for(i=1;i
dijkstrloyd
LV 7
@ 2013-10-28 23:47:03
