疯狂的火神

题目描述

火神要挑战 n 个人。 有t分钟的时间。 每个人的价值由一个三元组( a ,b, c )组成，表示如果火神在第x分钟单挑完这个人，他就会得到 a -b* x 的经验值，并且他需要c分钟来打倒这个人。 问最多能获得多少经验值？

数据范围

对于100%的数据1≤ n ≤1000,1≤t≤3000,1≤ Ci ≤t, Ai ≤10^6 保证每个人贡献的经验值到训练结束都不会变成负数。

题解

假设先打第 i 个人比先打第j个人更优，设当前的时刻为 K ，则满足

Ai−Bi∗(K+Ci)+Aj−Bj∗(K+Ci+Cj)> Aj−Bj∗(K+Cj)+Ai−Bi∗(K+Cj+Ci)

（ i ,j为连续两个人） 化简，得

BiCi > BjCj

我们就按照 BiCi 从大到小排序确定优先选择顺序。

剩下的，只需按照优先顺序选择某些人来单挑就可以了。这相当于一个背包问题，使用动态规划来解决。 Fi 表示恰好用了 i 分钟的最高经验值。 状态转移方程为Fi= max ( Fi ， Fi−Cj + Aj - Bj∗i )。 答案为 Max1<=i<=tFi 。

Code(Pascal)

var sh:array[0..2000] of extended; jy:array[0..2000,1..3] of longint; f:array[-5000..5000]of int64; t,n,y,i,o,l,time:longint; ans:int64; procedure qsort(l,r:longint); var i,j:longint; m:extended; begin i:=l; j:=r; m:=sh[(l+r) div 2]; repeat while sh[i]>m do inc(i); while sh[j]<m do dec(j); if i<=j then begin sh[0]:=sh[i]; sh[i]:=sh[j]; sh[j]:=sh[0]; jy[0]:=jy[i]; jy[i]:=jy[j]; jy[j]:=jy[0]; inc(i); dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; function max(a,b:int64):int64; begin if a>b then exit(a) else exit(b); end; begin readln(t); for y:=1 to t do begin readln(n,time); for i:=1 to n do begin readln(jy[i,1],jy[i,2],jy[i,3]); sh[i]:=jy[i,2]/jy[i,3]; end; qsort(1,n); for l:=-time to time do f[l]:=-maxlongint; f[0]:=0; for i:=1 to n do for l:=time downto 1 do f[l]:=max(f[l],f[l-jy[i,3]]+jy[i,1]-jy[i,2]*l); ans:=0; for i:=1 to time do ans:=max(ans,f[i]); writeln(ans); end; end.