NOIPの模拟_2016_8_14_t2_疯狂的火神

时间：2021-04-07 20:46:43

题目

Description

火神为了检验zone的力量，他决定单挑n个人。
由于火神训练时间有限，最多只有t分钟，所以他可以选择一部分人来单挑，由于有丽子的帮助，他得到了每个人特定的价值，每个人的价值由一个三元组(a,b,c)组成，表示如果火神在第x分钟单挑这个人（x指单挑完这个人的时间），他就会得到a-b*x的经验值，并且他需要c分钟来打倒这个人。
现在火神想知道，他最多可以得到多少经验值，由于火神本来就很笨，进入zone的疯狂的火神就更笨了，所以他希望你来帮他计算出他最多可以得到多少经验值。

Input

第一行一个正整数T，表示数据组数
对于每组数据，第一行为两个正整数n和t，表示跟火神单挑的人的个数和火神的训练时间。
下面n行，每行三个正整数Ai,Bi,Ci，表示每个人的价值，含义见题目。

Output

对于每组数据输出一行一个整数表示火神最多能得到多少经验值

Sample Input

1
4 10
110 5 9
30 2 1
80 4 8
50 3 2

Sample Output

88

Data Constraint

对于 20%的数据1≤n≤10
对于50%的数据1≤n≤18
对于100%的数据1≤n≤1000,1≤t≤3000,1≤Ci≤t,Ai≤10^6
保证n>200的数据组数不超过五组，其他的数据组数不超过10组
保证每个人贡献的经验值到训练结束都不会变成负数

题目大意

有很多样物品，每样物品只有一件，每次你选择一件物品，需要用一定的时间才可以获得这件物品，而且在这期间不能拿其他的物品，每一个物品都有一个贡献值，而且随着时间的推移每一件物品的贡献值都会有规律的下降，问怎么样选取可以获得最大的贡献值

比赛时の想法

比赛的时候并没有想到正解（以前做过一道一样的题目，但是忘记了QAQ）于是就打了50分的状压DP，然而打挂了/(ㄒoㄒ)/~~于是就愉快的爆零

正解

假设我们现在已经确定了要选择哪一些物品，现在我们想知道对于两件物品 i和j 哪一件物品哪一件先选更优，我们假设先选择 ai 更优，那么我们会得到一条不等式： a[i]+a[j]−b[i]∗(x+c[i])−b[j]∗(x+c[i]+c[j])>a[i]+a[j]−b[j]∗(x+c[j])−b[i]∗(x+c[i]+c[j]) 化简后可得： bi/ci>bj/cj （x是当i和j都还没有做时的时间）
于是我们发现对于i和j选取的先后顺序只和 b/c 有关系，所以我们可以对于每一个i的 bi/ci 从大到小排一次序，在按照这个顺序DP，这样就可以保证在选择的物品相同的情况下DP的结果是最优的。DP的话就是一个最基础的有限背包， f[i]:=max(f[i],f[i−c[j]]+a[j]−b[j]∗i)

贴代码

var
    a:array[0..1005,1..3]of longint;
    ex:array[0..1005]of extended;
    f:array[0..3005]of longint;
    i,j,k,l,n,x,y,t,o,ans:longint;
procedure qsort(l,r:longint);
var
    i,j:longint;
    mid:extended;
begin
    i:=l;
    j:=r;
    mid:=ex[(i+j) div 2];
repeat
while ex[i]>mid do inc(i);
while ex[j]<mid do dec(j);
if i<=j then
begin
            ex[0]:=ex[i];
            ex[i]:=ex[j];
            ex[j]:=ex[0];
            a[0]:=a[i];
            a[i]:=a[j];
            a[j]:=a[0];
            inc(i);
            dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
begin
    readln(o);
for o:=1 to o do
begin
        readln(n,t);
for i:=1 to n do readln(a[i,1],a[i,2],a[i,3]);
for i:=1 to n do ex[i]:=a[i,2]/a[i,3];
        qsort(1,n);
        fillchar(f,sizeof(f),0);
for j:=1 to n do
for i:=t downto a[j,3] do
                f[i]:=max(f[i],f[i-a[j,3]]+a[j,1]-a[j,2]*i);
        ans:=0;
for i:=1 to t do if f[i]>ans then ans:=f[i];
        writeln(ans);
end;
end.
标签：

相关文章