题目链接: https://vjudge.net/contest/540876#problem/C

题意

城镇中有 n 个位置，有 m 个烟花要放。第 i 个烟花放出的时间记为 t[i]，放出的位置记为 a[i]。如果烟花放出的时候，你处在位置 j，那么你将收获 b[i]-abs(j-a[i]) 点快乐值。

初始你可在任意位置，你每个单位时间可以移动不大于 d 个单位距离。求能够获得的最大的快乐值。

保证烟花按发射时间从早到晚的顺序给出。

(1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n)

(1 ≤ ai ≤ n; 1 ≤ bi ≤ 109; 1 ≤ ti ≤ 109)

思路

令 dp[i][j] 为第 i 个烟花发射后，当前位置为 j 能获得的最大快乐值。

dp[i][j] = max({dp[i-1][k]}) + (b[i]-abs(j-a[i]))，其中 k 可取值为位置 j 可在时间 t[i]-t[i-1] 可到达的范围。

显然对于这个 max 操作，对每一个 j 进行暴力枚举求最大值是不可行的，这样做的时间复杂度是 O(m·n·n)。必然会炸。

考虑在枚举 j 的时候，下一个 j 可抵达的范围 k 和上一个 j 大部分相同。所以只需要维护一个单调队列，队首存放当前 j 能达到的范围中能带来最大快乐值的 dp[i-1][k] 即可。

复杂度 O(m·n)。

代码

#include <iostream>
#include <cmath>
#include <cstring>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

const int maxN = 2e5+5;
int a[305], b[305], t[305];
long long dp[2][maxN];
int q[maxN];

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  int n, m, d; std::cin >> n >> m >> d;
  bool md = 0;
  orep(k, 0, m) {
    std::cin >> a[k] >> b[k] >> t[k];
    md = !md;
    int l = 0, r = 0;
    int j = 0;
    orep(i, 0, n) {
      const long long w = k ? 1ll*d*(t[k]-t[k-1]) : 0;
      for(; j < n && j <= i + w; ++j) {
        while(l!=r && dp[!md][j] > dp[!md][q[r-1]]) { --r; }
        q[r++] = j;
      }
      while(l!=r && q[l] < i - w) { l++; }
      dp[md][i] = dp[!md][q[l]] + b[k] - abs(a[k] - (i+1));
    }
  }
  long long ret = dp[md][0];
  orep(i, 1, n) { ret = std::max(dp[md][i],ret); }
  std::cout << ret;

  return 0;
}