题解 P1853 【投资的最大效益】

shaosimo · 2019-07-31 20:26:05 · 题解

看到没Pascal题解就赶紧来水一发

咳咳，进入正题。 这题 显而易见 是完全背包问题。难度不大，就是数据大了点。接下来上代码。

var t,m,i,j,n,sum,s:longint;//别吐槽我代码难看
a,b:array[0..10000000]of longint;
dp:array[0..10000000]of longint;
function max(a,b:longint):longint;
//为什么pascal没max函数
begin
if a>b then exit(a)
     else exit(b);
end;
begin
readln(t,n,m);
for i:=1 to m do
  read(a[i],b[i]);//输入
for sum:=1 to n do//完全背包的次数
  begin
  for i:=1 to m do//标准完全背包
    for j:=a[i] to t do
      dp[j]:=max(dp[j],dp[j-a[i]]+b[i]);
      //完全背包方程
  t:=t+dp[t];//记录答案
  end;
writeln(t);//输出
end.

第一次眼瞎没看到数据范围，WA了7个点，说多了都是泪。

看记录详情

另附标准01背包

//原谅我把数据吃了
function max(a,b:longint):longint;
begin
if a>b then exit(a)
       else exit(b);
end;
begin
readln(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
      dp[j]:=max(dp[j],dp[j-a[i]]+b[i]);
writeln(dp[t]);
end.

溜了溜了......