题目

代码

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 4e3 + 5;
int N, M, K, T;
int f[SIZE][SIZE];
int now, ans;
int head = 1, tail = 1, q[SIZE];

int IN() {
  char ch = getchar();
  int x = 0, f = 1;
  while (!isdigit(ch)) {
    if (ch == '-')
      f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}

void Insert(int x) {
  while (f[now - 1][x] > f[now - 1][q[tail]] && tail >= head)
    tail--;
  q[++tail] = x;
}

void Clear() {
  head = tail = 1;
  q[1] = 0;
}

int Find(int x) {
  if (x + T <= M)
    Insert(x + T);
  while (q[head] < x - T)
    head++;
  return q[head];
}

void DP() {
  for (now = 2; now <= N; now++) {
    for (int i = 1; i <= T; i++)
      Insert(i);
    for (int i = 1; i <= M; i++)
      f[now][i] += f[now - 1][Find(i)];
    Clear();
  }
}

int main() {
  q[0] = 0x7ffffff;
  cin >> N >> M >> K >> T;
  for (int i = 1; i <= K; i++)
    f[IN()][IN()] = IN();
  DP();
  for (int i = 1; i <= M; i++)
    ans = max(ans, f[N][i]);
  cout << ans;
  system("pause");
  return 0;
}