bzoj 1207 DP

　　我们用w[i]表示到第i个地鼠出现的时候，我们选了第i个地鼠，能得到的最大的价值，那么显然有转移w[i]=w[j]+1(time[i]-time[j]>=abs(x[i]-x[j])+abs(y[i]-y[j]))。每次转移为O(1)的，一共转移了Σi(i<=m)次，所以时间复杂度为m^2/2。

    Problem: 1207
    User: BLADEVIL
    Language: C++
    Result: Accepted
    Time:2708 ms
    Memory:960 kb
****************************************************************/
 
//By BLADEVIL
#include <cstdio>
#include <algorithm>
#define maxm 10010
 
using namespace std;
 
int n,m,ans;
int time[maxm],x[maxm],y[maxm],w[maxm];
 
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%d%d%d",&time[i],&x[i],&y[i]);
    for (int i=1;i<=m;i++){
        w[i]=1;
        for (int j=1;j<=i-1;j++) 
            if (time[i]-time[j]>=abs(x[i]-x[j])+abs(y[i]-y[j])) w[i]=max(w[i],w[j]+1);
        ans=max(ans,w[i]);
    }
    printf("%d
",ans);
    return 0;
}