经本人N次提交后确认:此题输入的价值有负数!!!
(至少5个点价值有负数)
以下是本人最后两次提交(由此二次才正式确认有负数,请大家以下多思考一下):
第一次:
program rq162;
var a:array [0..10000] of longint;
w,v,i,j,m,n:longint;
begin
readln(n,m); a[0]:=0;
for i:=1 to m do a[i]:=-1(注意此处不同);
for i:=1 to n do
begin
readln(w,v);
for j:= w to m do
if (a[j]<a[j-w]+v) then a[j]:=a[j-w]+v;
end;
writeln(a[m]);
readln;
end.
第二次:
program rq162;
var a:array [0..10000] of longint;
w,v,i,j,m,n:longint;
begin
readln(n,m); a[0]:=0;
for i:=1 to m do a[i]:=-maxlongint(除此处外都完全相同);
for i:=1 to n do
begin
readln(w,v);
for j:= w to m do
if (a[j]<a[j-w]+v) then a[j]:=a[j-w]+v;
end;
writeln(a[m]);
readln;
end.
看起来应该都是正确的,但是---------------------------------------------
第一次:
有效耗时: 1016毫秒
测试结果1: 通过本测试点|有效耗时203ms
测试结果2: 测试结果错误.错误结果为:12433881
正确结果应为:12413605
测试结果3: 测试结果错误.错误结果为:13634694
正确结果应为:13630798
测试结果4: 测试结果错误.错误结果为:16957369
正确结果应为:16950743
测试结果5: 通过本测试点|有效耗时219ms
测试结果6: 通过本测试点|有效耗时203ms
测试结果7: 测试结果错误.错误结果为:11152651
正确结果应为:11144826
测试结果8: 通过本测试点|有效耗时188ms
测试结果9: 测试结果错误.错误结果为:6457267
正确结果应为:6450430
测试结果10: 通过本测试点|有效耗时203ms
第二次:
有效耗时: 1921毫秒
测试结果1: 通过本测试点|有效耗时203ms
测试结果2: 通过本测试点|有效耗时172ms
测试结果3: 通过本测试点|有效耗时218ms
测试结果4: 通过本测试点|有效耗时172ms
测试结果5: 通过本测试点|有效耗时219ms
测试结果6: 通过本测试点|有效耗时203ms
测试结果7: 通过本测试点|有效耗时172ms
测试结果8: 通过本测试点|有效耗时187ms
测试结果9: 通过本测试点|有效耗时172ms
测试结果10: 通过本测试点|有效耗时203ms
严重鄙视RQ的数据~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
楼主你的背包是不对滴......
f[i][j]:=max(f[i-1][j],f[i-1][j-v[i]]+p[i]);
这个是正解........而且不用讨论负数.......
负数的话会被舍掉的......
求最大值的背包,不用初始化数组....
还有我的评测器有问题.......O(n^2)的复杂度会超时.......明显bug........