题目描述

岩石怪物杜达生活在魔法森林中，他在午餐时收集了N块能量石准备开吃。

由于他的嘴很小，所以一次只能吃一块能量石。

能量石很硬，吃完需要花不少时间。

吃完第 i 块能量石需要花费的时间为SiSi秒。

杜达靠吃能量石来获取能量。

不同的能量石包含的能量可能不同。

此外，能量石会随着时间流逝逐渐失去能量。

第 i 块能量石最初包含EiEi单位的能量，并且每秒将失去LiLi单位的能量。

当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。

能量石中包含的能量最多降低至0。

请问杜达通过吃能量石可以获得的最大能量是多少？

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含整数N，表示能量石的数量。

接下来N行，每行包含三个整数Si,Ei,LiSi,Ei,Li。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case #x: y”，其中x是组别编号（从1开始），y是可以获得的最大能量值。

数据范围

1≤T≤101≤T≤10,
1≤N≤1001≤N≤100,
1≤Si≤1001≤Si≤100,
1≤Ei≤1051≤Ei≤105,
0≤Li≤105

样例

输入样例：

3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0
输出样例：

Case #1: 105
Case #2: 8
Case #3: 500
样例解释

在样例＃1中，有N = 4个宝石。杜达可以选择的一个吃石头顺序是：

吃第四块石头。这需要5秒，并给他80单位的能量。
吃第二块石头。这需要5秒，并给他5单位的能量（第二块石头开始时具有30单位能量，5秒后失去了25单位的能量）。
吃第三块石头。这需要100秒，并给他20单位的能量（第三块石头开始时具有30单位能量，10秒后失去了10单位的能量）。
吃第一块石头。这需要20秒，并给他0单位的能量（第一块石头以10单位能量开始，110秒后已经失去了所有的能量）。
他一共获得了105单位的能量，这是能获得的最大值，所以答案是105。

在样本案例＃2中，有N = 3个宝石。

无论杜达选择吃哪块石头，剩下的两个石头的能量都会耗光。

所以他应该吃第三块石头，给他提供8单位的能量。

在样本案例＃3中，有N = 2个宝石。杜达可以：

吃第一块石头。这需要12秒，并给他300单位的能量。
吃第二块石头。这需要5秒，并给他200单位的能量（第二块石头随着时间的推移不会失去任何能量！）。
所以答案是500。

难度： 困难
时/空限制： 1s / 64MB
总通过数： 1298
总尝试数： 2346
来源： Google Kickstart2019 Round B Problem B
算法标签
挑战模式  

算法1

C++ 代码(重载运算符)

#include<bits/stdc++.h>
using namespace std;
const int N=105,S=10005;
int n;
int f[S];
struct node{
    int s,e,l;
    bool operator<(const node &W)const
    {
        return s*W.l<l*W.s;
    }
}a[N];
/*bool cmp(node x,node y)
{
    return x.s*y.l<x.l*y.s;
}
*/
int main() 
{
    int T,cnt=0; 
    scanf("%d",&T);
    while(T--) 
    {
        memset(f,0,sizeof f);
        scanf("%d",&n);
        int t=0;
        for(int i=1,s,e,l;i<=n;i++) 
        {
            scanf("%d%d%d",&s,&e,&l);
            t+=s; 
            a[i]=(node){ s, e, l }; 
        }
        //sort(a+1,a+1+n,cmp);
        sort(a+1,a+1+n);
        f[0]=0;
        for(int i=1;i<=n;i++) 
        {
            for(int j=t;j>=a[i].s; j--)
                f[j]=max(f[j],f[j-a[i].s]+max(0,a[i].e-(j-a[i].s)*a[i].l));
        }
        int res=0;
        for(int i=1;i<=t;i++) res=max(res,f[i]);
        printf("Case #%d: %d\n",++cnt,res);
    }
    return 0;
}

算法2

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=105,S=10005;
int n;
int f[S];
struct node{
    int s,e,l;
}a[N];
bool cmp(node x,node y)
{
    return x.s*y.l<x.l*y.s;
}
int main() 
{
    int T,cnt=0; 
    scanf("%d",&T);
    while(T--) 
    {
        memset(f,0,sizeof f);
        scanf("%d",&n);
        int t=0;
        for(int i=1,s,e,l;i<=n;i++) 
        {
            scanf("%d%d%d",&s,&e,&l);
            t+=s; 
            a[i]=(node){ s, e, l }; 
        }
        sort(a+1,a+1+n,cmp);
        f[0]=0;
        for(int i=1;i<=n;i++) 
        {
            for(int j=t;j>=a[i].s; j--)
                f[j]=max(f[j],f[j-a[i].s]+max(0,a[i].e-(j-a[i].s)*a[i].l));
        }
        int res=0;
        for(int i=1;i<=t;i++) res=max(res,f[i]);
        printf("Case #%d: %d\n",++cnt,res);
    }
    return 0;
}