题解

知识点：

DP，方格类最优值DP，单调队列优化DP

分析：

相信这道题大家都知道肯定是DP，然而非常简单地想到，从上一层的每个点枚举走到这个点的最大值。

一开始看到这个数据范围我就觉得可以硬做，但是又想到这样的裸的DP是$O(n^3)$的，不能通过所有的测试点。然后我想到了单调队列优化DP，可以优化到$O(n^2)$，当然这样是正确的解法，但是我又觉得细节有点多，还不如我写一个带log的数据结构去优化DP，然后我就写了一棵线段树维护区间最大值，但是常数太大还是TLE了最后一个点，用ST表写反而WA了8个点。最后不得不再次观察数据范围。

发现其实k的值非常小（与n同阶）。所以考虑先把所有有值的点按照x轴来排序（从上往下），然后进行DP。枚举之前行的点，因为每一行跳t步的话，x行最多可以跳xt步，那么判断$\Delta y$与$\Delta x\times t$之间的关系，如果前者不大于后者，那么代表走得到，就可以转移。这样求最大值，复杂度是$O(n^2)$的，而且常数很小，值得推荐。

代码：

#include<cstdio>
//#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=4010;
int n,m,k,t,f[maxn],ans;
struct node
{
	int x,y,v;
}a[maxn];

bool cmp(node a,node b)
{
	return a.x<b.x;
}

int main()
{
	int i,j;
	scanf("%d%d%d%d",&n,&m,&k,&t);
	for (i=1;i<=k;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
	sort(a+1,a+k+1,cmp);//排序
	f[1]=a[1].v;//初始值即为取走它自己的值
	for (i=1;i<=k;i++)
	{
		for (j=0;j<i;j++)
			if (abs(a[i].y-a[j].y)<=t*abs(a[i].x-a[j].x))//走不走得到
				f[i]=max(f[i],f[j]+a[i].v);//走得到就转移
		ans=max(ans,f[i]);//在过程中就可以求最大值了（因为v有可能是非正数）
	}
	printf("%d\n",ans);
	return 0;
}

从这道题，我们可以发现，当一些题目n不小的时候，可以观察其他约束条件，从简单的问题入手，往往可以收获更好的结果。