对于一个$n imes m$的矩形，我们只要对每一行求滑动窗口，当前位置的最大价值就是他上一行的滑动窗口（点击查看解释）+当前位置的价值。因为当前位置左上T个位置，会被他左边T个位置的点更新到，所以我们只需要算一边就好。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 const int maxn= 4005; 6 int N, M, K, T, val[maxn][maxn], f[maxn][maxn], g[maxn]; 7 int head, tail, q[maxn]; 8 int main() { 9 cin >> N >> M >> K >> T; 10 for (register int i = 1; i <= K; ++i) { 11 int x, y, z; 12 scanf("%d%d%d", &x, &y, &z); 13 val[x][y] = z; 14 } 15 memset(f, -0x3f, sizeof(f)); 16 for (int i = 1; i <= M; ++i) 17 f[1][i] = val[1][i]; 18 tail = 0, head = 1; 19 for (register int i = 2; i <= N; ++i) { 20 q[head = 0] = q[tail = 1] = 0; 21 for (register int j = 1; j <= M; ++j) { 22 while (head <= tail && j - q[head]>T) head++; 23 while (head <= tail && f[i - 1][q[tail]] <= f[i - 1][j]) tail--; 24 q[++tail] = j, g[j] = f[i - 1][q[head]]; 25 } 26 for (register int j = 1; j <= M; ++j) { 27 int l = j, r = min(j + T, M); 28 f[i][j] = max(g[l], g[r]) + val[i][j]; 29 } 30 } 31 int Ans = -2e9; 32 for (int i = 1; i <= M; ++i) 33 Ans = max(Ans, f[N][i]); 34 printf("%d ", Ans); 35 return 0; 36 }