LuoGu: CF372C Watching Fireworks is Fun
CF: C. Watching Fireworks is Fun
先考虑暴力DP，$f _ {i, j}$ 表示当前放第 $i$ 个烟花在 $j$ 位置要获得的最大开心值。那么 $f _ {i, j} = (\max _ {k = j - \Delta t d} ^ {j + \Delta td} f_{i - 1, k}) + b _ i - \left | a _ i - j \right |$ ，对于每个 $i$ 和 $j$ 枚举所有可行 $k$ ，可以将 $f _ {i, j}$ 算出来。时间复杂度 $O(n ^ 2 m)$ ，显然是不能通过的。
考虑如何优化。不难发现，当 $i$ 固定了，那么 $\Delta td$ 也是固定的，那么就是取一段 $2\Delta td$ 长度的滑动窗口，所以可以考虑使用单调队列。对于每个 $j$ 先将所有的 $j + \Delta td$ 的元素补齐，将多余的元素删除，即可维护当前 $j$ 的队列。注意判断边界，位置不能大于 $n$ 不能小于 $1$ 。最终的答案就是 $\max_{i = 1} ^ n f _ {m, i}$ 。再考虑空间问题，空间复杂度为 $O(nm)$ ，实际上可以将 $m$ 一维滚动掉。
查看代码
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
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 15e4 + 10, M = 310;
const LL inf = 1e18;
LL A[M], B[M], t[M], f[2][N];
int n, m, d;
int hd, tl, q[N];
int main()
{
scanf("%d%d%d", &n, &m, &d);
for (int i = 1; i <= m; i++)
scanf("%lld%lld%lld", &A[i], &B[i], &t[i]);
for (int i = 1; i <= n; i++)
f[0][i] = 0;
for (int i = 1; i <= n; i++)
f[1][i] = -inf;
for (int i = 1, k; i <= m; i++)
{
k = 1;
hd = 1, tl = 0;
LL dis = d * (t[i] - t[i - 1]);
for (int j = 1; j <= n; j++)
{
for (; k <= min((LL)n, j + dis); k++)
{
while (hd <= tl && f[i - 1 & 1][q[tl]] <= f[i - 1 & 1][k])
tl--;
q[++tl] = k;
}
while (hd <= tl && q[hd] < max(1ll, j - dis))
hd++;
f[i & 1][j] = f[i - 1 & 1][q[hd]] - abs(A[i] - j) + B[i];
}
}
LL mx = -inf;
for (int i = 1; i <= n; i++)
mx = max(mx, f[m & 1][i]);
printf("%lld", mx);
return 0;
}
|