题目：洛谷-p2285
思路：
首先说一个究极坑点：居然用结构体就TLE,数组就能够AC。(第一次被这样恶心到。。)
思路:
一开始以为是地图dp,仔细思考后首先三维空间太大,而且也难以dp。
因为time是按递增顺序给出。那么显然对于第i个地鼠,如果从第i-1个地鼠到第i个地鼠的时间>=他们的曼哈顿距离。
就可以从i-1到i。
那么这里就很像是最长递增子序列了。
所以dp转移即可。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e4+5; const int M = 1e6+5; const int Mod = 998244353; #define pi acos(-1) #define INF 1e27 #define INM INT_MIN #define pb(a) push_back(a) #define mk(a,b) make_pair(a,b) #define dbg(x) cout << "now this num is " << x << endl; #define met0(axx) memset(axx,0,sizeof(axx)); #define metf(axx) memset(axx,-1,sizeof(axx)); #define sd(ax) scanf("%d",&ax) #define sld(ax) scanf("%lld",&ax) #define sldd(ax,bx) scanf("%lld %lld",&ax,&bx) #define sdd(ax,bx) scanf("%d %d",&ax,&bx) #define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx) #define sfd(ax) scanf("%lf",&ax) #define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx) #define pr(a) printf("%d\n",a) #define plr(a) printf("%lld\n",a) int n,m,dp[N],x[N],y[N],t[N]; int main() { sdd(n,m); for(int i=1;i<=m;++i) sddd(t[i],x[i],y[i]); int ans = 0; for(int i=1;i<=m;++i) { dp[i] = 1; for(int j=1;j<i;++j) { int dis = abs(x[i]-x[j])+abs(y[i]-y[j]); if(dis <= (t[i]-t[j])) dp[i] = max(dp[i],dp[j]+1); } ans = max(ans,dp[i]); } pr(ans); // system("pause"); return 0; }