CF1430F Realistic Gameplay

发表于 | 阅读数

有$n$波怪物，你有一把枪，枪的弹夹量为$k$，第$i,[l_i,r_i]$波怪物数量为$a_i$，使用子弹不费时间，但是你每次换弹都需要将弹夹（包括里面的子弹）扔掉，在尽量保证通关的情况下，需要的最多的子弹数为多少。

有几点需要明确:

  • 如果怪物之间有多出的时间，那么我可以选择换弹来达到最优的状态。
  • 对于一波怪物你最多可以打出=$起始子弹+k(r[i]-l[i])$。
  • 最优一定是一次不换弹，我们只需要减少换弹次数即可。
  • 因为后面如果特别紧，这个时候就必须换，这样也可让后面更轻松。

我们就可以预处理出每波进场需要的最少的子弹。考虑连在一起的怪物波，直接从后往前$dp$即可。(把后一次需要的子弹当成多出的怪物)。

然后就是贪心的要换子弹，就可以换子弹。

  • 当我带着$tmp$子弹进场。在我不浪费子弹并且可以杀完所有怪物的情况下，我最后剩余的子弹应该是$(k - (a[i] - tmp) \mod k) \mod k$

然后贪心的模拟一遍即可。（连续部分可以选择合并起来模拟，也可以不合并）

代码 
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
48
49
50
51
52
53
54
55
56

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

int main()
{
    int n = read(), k = read();
    vector<ll> l(n + 1), r(n + 1), a(n + 1), f(n + 1);
    for (int i = 1; i <= n; i++)
        l[i] = read(), r[i] = read(), a[i] = read();
    for (int i = n; i >= 1; i--)
    {
        if (r[i] == l[i + 1])
        {
            f[i] = max(0ll, f[i + 1] + a[i] - (r[i] - l[i]) * k);
        }
        else
        {
            f[i] = max(0ll, a[i] - (r[i] - l[i]) * k);
        }
        if (f[i] > k)
            return puts("-1");
    }
    ll tmp = k, ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += a[i];
        if (f[i] > tmp)
        {
            ans += tmp;
            tmp = k;
        }
        tmp = (k - (a[i] - tmp) % k) % k;
    }
    cout << ans << endl;
}