萌新求助单调队列优化 dp,WA on #6
查看原帖
萌新求助单调队列优化 dp,WA on #6
709949
M1rac0楼主2022/8/14 16:09
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 15e4 + 5, M = 305;
int n, m, d, a[M], b[M], tim[M], h, t, q[M], f[2][N], ans = -1e18;
signed main() {
  scanf("%I64d %I64d %I64d", &n, &m, &d);
  for (int i = 1; i <= m; ++i)
    scanf("%I64d %I64d %I64d", &a[i], &b[i], &tim[i]);
  for (int i = 1; i <= m; ++i) {
    h = 1, t = 0;
    for (int j = 1; j <= n; ++j) {
      f[i & 1][j] = f[i - 1 & 1][j];
      while (h <= t && q[h] + (tim[i] - tim[i - 1]) * d < j) h++;
      while (h <= t && f[i - 1 & 1][q[t]] < f[i - 1 & 1][j]) t--;
      q[++t] = j;
      f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][q[h]]);
    }
    h = 1, t = 0;
    for (int j = n; j > 0; --j) {
      while (h <= t && q[h] - (tim[i] - tim[i - 1]) * d > j) h++;
      while (h <= t && f[i - 1 & 1][q[t]] < f[i - 1 & 1][j]) t--;
      q[++t] = j;
      f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][q[h]]);
    }
    for (int j = 1; j <= n; ++j) {
      f[i & 1][j] += b[i] - abs(a[i] - j);
      if (i == m) ans = max(ans, f[i & 1][j]);
    }
  }
  printf("%I64d\n", ans);
  return 0;
}

// 设 f[i][j] 表示时间 tim[i],地点 j 的最大开心值
// f[i][j] = max(f[i - 1][k]) + b[i] - abs(a[i] - j)
// (max(1, j - (tim[i] - tim[i - 1]) * d) <= k <= min(n, j + (tim[i] - tim[i - 1]) * d))
2022/8/14 16:09
加载中...