题目背景
据说在红雾异变时，博丽灵梦单身前往红魔馆，用十分强硬的手段将事件解决了。
然而当时灵梦在Power达到MAX之前，不具有“上线收点”的能力，所以她想要知道她能收集多少P点，然而这个问题她答不上来，于是她找到了学OI的你。
题目描述
可以把游戏界面理解成一个N行M列的棋盘，有K个格子上有P点，其价值为val(i,j)
初始灵梦可以选择在第一行的任意一个格子出发，每秒她必须下移一格。
灵梦具有一个左右移动的速度T，可以使她每秒向左或右移动至多T格,也可以不移动，并且不能折返。移动可视为瞬间完成，不经过路途上的点，只能获得目标格子的P点。
求最终她能获得的POWER值最大是多少？
输入输出格式
输入格式：
第一行四个数字，N,M,K,T
接下来K行每行3个数字x,y,v,代表第x行第y列有一个val为v的P点，数据保证一个格子上最多只有1个P点。
输出格式：
一个数字
输入输出样例
输入样例#1：
3 3 4 1
1 1 3
1 2 1
2 2 3
3 3 3
输出样例#1：
9
说明
对于40%的测试点，1<=N,M,T,K<=200
对于100%的测试点，1<=N,M,T,K<=4000
v<=100，N,M,K,T均为整数
by-szc
朴素dp好想，然后随便套一个st表或单调队列搞一搞，把转移变成O1
#include<cstdio>
#include<algorithm>
const int maxn = ;
inline int read() {
int x=, f=;
char c=getchar() ;
while(c<''||c>''){ if(c=='-')f=-;c=getchar();};
while(c<=''&&c>='')x=x*+c-'',c=getchar();
return x*f;
}
int n,m,k,t,map[maxn][maxn];
int dp[maxn][maxn],q[maxn];
int main() {
n=read(),m=read(),k=read(),t=read();
for(int a,b,c,i=;i<=k;++i) {
a=read(),b=read();
c=read();
map[a][b]=c;
}
for(int i=;i<=n;++i) {
int head=,tail=;
for(int j=;j<=t;++j) {
while(dp[i-][q[tail]]<=dp[i-][j]&&head<=tail)tail--;
q[++tail]=j;
}
for(int j=;j<=m;++j) {
while(q[head]<j-t&&head<=tail)head++;
if(j+t<=m) {
while(dp[i-][q[tail]]<=dp[i-][j+t]&&head<=tail)tail--;
q[++tail]=j+t;
}
dp[i][j]=dp[i-][q[head]]+map[i][j];
}
}
int ans=;
for(int i=;i<=m;++i) {
ans=std::max(ans,dp[n][i]);
}
printf("%d\n",ans);
return ;
}