Realistic Gameplay | Codefoces 1430F

题目链接

你有一把枪,枪的弹匣量为 \(k\)

\(n\) 波怪物,对于第 \(i\) 波,你必须在 \([l_i,r_i]\) 时间内消灭 \(a_i\) 只怪物 \((r_i \le l_{i+1})\),你可以在任意时刻打出一发子弹击杀一只怪物且不耗费时间。你每次换弹都需要将弹匣(包括里面的子弹)扔掉,并花费 1 单位的时间。

在保证通关的情况下,需要的最少的子弹数为多少。

\(n \le 2000,k \le 10^9, l_i \le r_i \le 10^9,a_i \le 10^9\)

考虑什么时候会换弹,要么是当前子弹打完了,而这波怪还没打完,称之为一类换弹;要么是当前这波怪已经打完了,但为了通关而换新弹匣 ,称之为二类换弹。

如果所有二类换弹在哪一波都是确定的,只要按时间线扫描一遍就可以算出所有一类换弹的时间。

因此设 \(f_i\) 表示打完前 \(i\) 波怪,且在第 \(i\) 波进行一次二类换弹需要的最少的子弹数。
转移就从第 \(i + 1\) 波开始扫描,同时维护当前弹匣中的子弹数,直到不合法为止。
如果在 \(r_j\) 之前消灭了第 \(j\) 波的所有怪物,就可以在第 \(j\) 波进行一次二类换弹后转移到 \(f_j\)
如果能消灭完所有怪就更新 ans

复杂度 \(O(n^2)\)

代码:

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
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define upd(a, b) (a = min(a, b))

using namespace std;
const int N = 2005;
typedef long long ll;
int n, K;
int l[N], r[N], a[N];
ll f[N];
int main() {
mem(f, 63), f[0] = 0;
cin >> n >> K;
rep(i, 1, n) scanf("%d%d%d", &l[i], &r[i], &a[i]);
rep(i, 0, n - 1) {
int nw = K;
rep(j, i + 1, n) {
int t = (a[j] - nw + K - 1) / K;
if(t > r[j] - l[j]) break;
nw += t * K - a[j];
f[i] += a[j];
if(j == n) upd(f[j], f[i]);
else if(t < l[j + 1] - l[j]) upd(f[j], f[i] + nw);
}
}
if(f[n] < 0x3f3f3f3f3f3f3f3f) cout << f[n];
else puts("-1");
return 0;
}