var f:array [0..10000] of longint;
w,v:array [1..5000] of integer;
i,j,n,m:integer;
function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end;
begin
readln(n,m);
for i:=1 to n do
readln(w[i],v[i]);
fillchar(f,sizeof(f),0);
for i:=1 to m div w[1] do
f[i*w[1]]:=v[1]*i;
for i:=2 to n do
for j:=w[i] to m do
f[j]:=max(f[j],f[j-w[i]]+v[i]);
writeln(f[m]);
end.
PS:我的程序另5个点全部比标准答案大几千以上~
状态题目:奖金
题目编号:162-奖金 查看该题
状态: Accepted
测评机: Xeond[6]
得分: 100分
提交日期: 2008-10-14 21:55:00
有效耗时: 923毫秒
测试结果1: 通过本测试点|有效耗时110:ms
测试结果2: 通过本测试点|有效耗时63:ms
测试结果3: 通过本测试点|有效耗时125:ms
测试结果4: 通过本测试点|有效耗时62:ms
测试结果5: 通过本测试点|有效耗时140:ms
测试结果6: 通过本测试点|有效耗时94:ms
测试结果7: 通过本测试点|有效耗时78:ms
测试结果8: 通过本测试点|有效耗时94:ms
测试结果9: 通过本测试点|有效耗时63:ms
测试结果10: 通过本测试点|有效耗时94:ms
提交代码: #include<iostream>
#include<climits>
using namespace std;
int main(void){
long n,m,cost[10002],value[10002],dp[10002];
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>cost[i]>>value[i];
for (int i=1;i<=m;i++) dp[i]=LONG_MIN;
for (int i=1;i<=n;i++)
for (int j=cost[i];j<=m;j++)
if (dp[j-cost[i]]+value[i]>dp[j])
dp[j]=dp[j-cost[i]]+value[i];
cout<<dp[m];
return 0;
}