Post

AcWing734 - 能量石

AcWing734 - 能量石

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

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

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

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

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

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

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

第 i 块能量石最初包含 Ei 单位的能量,并且每秒将失去 Li 单位的能量。

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

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

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

输入格式

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

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

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

输出格式

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

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

数据范围

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

输入样例:

1
2
3
4
5
6
7
8
9
10
11
12
13
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

输出样例:

1
2
3
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。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;

struct Stone {
  int s, e, l;
  bool operator<(const Stone& rhs) const {
    return s * rhs.l < l * rhs.s;
  }
} stone[N];

int n;
int f[N];

int main() {
  int T;
  cin >> T;
  for (int C = 1; C <= T; C++) {
    int m = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
      int s, e, l;
      cin >> s >> e >> l;
      m += s;
      stone[i] = {s, e, l};
    }
    
    sort(stone, stone + n);
    
    memset(f, 0x8f, sizeof f);
    f[0] = 0;
    
    for (int i = 0; i < n; i++) {
      int s = stone[i].s, e = stone[i].e, l = stone[i].l;
      for (int j = m; j >= s; j--) 
        f[j] = max(f[j], f[j - s] + max(0, e - (j - s) * l));
    }
    
    int res = 0;
    for (int i = 0; i <= m; i++) res = max(res, f[i]);
    printf("Case #%d: %d\n", C, res);
  }
  
  return 0;
}
This post is licensed under CC BY 4.0 by the author.