考虑朴素的dp：
对于每一行的每一个点 枚举能到的所有点（类似bzoj1648 比这题简单的dp）
期望时间复杂度O(NMT)
显然是超时做法
那么我们发现只有k个点对答案有贡献 考虑对每一个有权值的点以x为关键字排序
容易看出 对于每个点前面的所有点，只要有abs(yi-yj)<=t*abs(xi-xj)
那么就可以从j转移到i
扫一遍即可 期望复杂度O(K2)
--------------其实和打鼹鼠差不多的题，只是自己打的时候想的是usaco的那道...我真是弱不可言orz-----------------
#pragma GCC optimize("O2")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<limits.h>
#include<ctime>
#define N 100001
typedef long long ll;
const int inf=0x3fffffff;
const int maxn=4017;
using namespace std;
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch>‘9‘|ch<‘0‘)
{
if(ch==‘-‘)
f=-1;
ch=getchar();
}
while(ch<=‘9‘&&ch>=‘0‘)
{
x=(x<<3)+(x<<1)+ch-‘0‘;
ch=getchar();
}
return f*x;
}
struct tsdl{
int x,y,w,dp;
}a[N];
bool cmp(tsdl a,tsdl b)
{
return a.x<=b.x;
}
int main()
{
int n=read(),m=read(),k=read(),t=read();
for(int i=1;i<=k;i++)
{
a[i].x=read(),a[i].y=read(),a[i].w=read();
}
sort(a+1,a+n+1,cmp);
a[1].dp=a[1]
for(int i=1;i<=k;i++)
{
for(int j=1;j<i;j++)
{
if(abs(a[i].y-a[j].y)<=t*abs(a[i].x-a[j].x))
a[i].dp=max(a[i].dp,a[j].dp+a[i].w);
}
}
int ans=0;
for(int i=1;i<=k;i++)
{
ans=max(ans,a[i].dp);
}
cout<<ans;
}
原文：http://www.cnblogs.com/tsunderehome/p/7562433.html