JZOJ链接 (原题BestCoder Round #59 (div.1) B) 题目大意直接看题吧 首先很容易想到这是一个一维的背包问题 但是由于不同的时间打怪有不同的效益 所以我们需要决定的是打怪的顺序 假设最优答案的打怪顺序为p1,p2,p3…pm 那么对于任意两个相邻怪物pi,pi+1 调换顺序不会使得其更优 由于两个怪物需要打的时间相同 所以调换两个相邻怪物不会使其他怪物的贡献有影响，因此我们只用关心两个相邻怪物就好了 依然是对于怪物i,i+1而言 如果我们先打i,我们失去的收益为 如果我们先打i+1,我们失去的收益为 因此如果,则先打pi更优 移项可得 由此可得最优的答案顺序中是递减的 因此我们把怪物的从大到小排列 之后就是一个一维背包问题了 设表示用i分钟达到的最大收益 转移公式为 最后统计其中最大的即可
代码
var a,b,c:array[0..1000] of longint; rt:array[0..1000] of extended; f:array[-3000..3000] of int64; tt,n,m,i,j,k:longint; ans:int64; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure qsort(l,r:longint); var i,j,t:longint; mid,et:extended; begin i:=l; j:=r; mid:=rt[(i+j) div 2]; repeat while rt[i]>mid do inc(i); while rt[j]<mid do dec(j); if i<=j then begin et:=rt[i];rt[i]:=rt[j];rt[j]:=et; t:=a[i];a[i]:=a[j];a[j]:=t; t:=b[i];b[i]:=b[j];b[j]:=t; t:=c[i];c[i]:=c[j];c[j]:=t; inc(i); dec(j); end; until i>j; if j>l then qsort(l,j); if i<r then qsort(i,r); end; begin readln(tt); repeat readln(n,m); for i := 1 to n do begin readln(a[i],b[i],c[i]); rt[i]:=b[i]/c[i]; end; qsort(1,n); fillchar(f,sizeof(f),0); for j := 1 to n do begin for i := m downto 0 do begin if i-c[j]>=0 then f[i]:=max(f[i],f[i-c[j]]+a[j]-i*b[j]); end; end; ans:=0; for i := 0 to m do if ans<f[i] then ans:=f[i]; writeln(ans); dec(tt); until tt=0; end.