[success]原题 https://www.luogu.org/problem/show?pid=2285[/success]

我的解法：
在学校举办的模拟赛上的题目，最近一直在做DP题...然后结果当时想了没半个小时AC了，
回来想在洛谷再A一次，结果等级居然说是提高+/省选- = =...这个分级有点水啊...

做法也很简单，从时间顺序逆着来DP，看这个点在规定时间能到达哪几个点
dp[i] = max{dp[j]|time(i, j) >= dist(i, j)}
然后还得特判...n==m==0 答案是2？？？？？？？？无语...
O(m^2)

代码:
[code lang="cpp"]
#include<cstdio>
#include<iostream>
#define MAXN 1050
#define MAXM 10050
using namespace std;
int v[MAXM];
int mo[MAXM][3];
int n, m;

int fabs(int i){
return (i)<0?-(i):(i);
}

int dist(int i, int j){
return fabs(mo[i][1] - mo[j][1]) + fabs(mo[i][2] - mo[j][2]);
}

int main(){
int ans = 1;
scanf("%d%d", &n, &m);
if (n == 0 && m == 0){
printf("2");
return 0;
}
for (int i = 0; i < m; i++) scanf("%d%d%d", &mo[i][0], &mo[i][1], &mo[i][2]);
v[m - 1] = 1;
for (int i = m - 1; i >= 0; i--){
int adds = -1;
for (int j = i + 1; j < m; j++) if (mo[j][0] - mo[i][0] >= dist(i, j)) adds = max(adds, v[j]);
v[i] = max(adds + 1, 1);
}
for (int i = 0; i < m; i++) ans = max(ans, v[i]);
printf("%d", ans);
}
[/code]

是不是除了dp我还得再做做其他类型的题目??