这道题刚开始以为很难，，后来发现很水，，果断敲代码后，悲剧就开始了，频繁TLE。。。。后来用动态规划的思想优化了一下，还是TLE。。最后用G++提交，却莫名其妙的ac了，而且只花了1453ms，，神奇。题目：
Jack's struggle
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 962 Accepted Submission(s): 336
Problem Description
A team of airborne troops are ready to complete some missions.
The battlefield was divided into a grid of n*n, this team can be air-dropped at any place on time 0. In every time unit after landing, they can go to the grid left, right, up or down to the current grid, or they can just stay.
On their mission list, each mission is described as three integers: t, r and c, represents a task that must be completed exactly at time t on the grid (r, c).
Obviously, with limits of time, not all missions can be done.
The captain, Jack, struggling making decisions, wants to know how many missions they can complete at most.
The battlefield was divided into a grid of n*n, this team can be air-dropped at any place on time 0. In every time unit after landing, they can go to the grid left, right, up or down to the current grid, or they can just stay.
On their mission list, each mission is described as three integers: t, r and c, represents a task that must be completed exactly at time t on the grid (r, c).
Obviously, with limits of time, not all missions can be done.
The captain, Jack, struggling making decisions, wants to know how many missions they can complete at most.
Input
The input contains serveral cases:
For each case:
* The first line contains two integers n and m, 1<=n<=1000, 1<=m<=10000, n represents the size of the battlefield and m represents the number of missions on the list.
* Following m lines, each one describes a mission using three integers, t, r and c.
No two missions have the same t, r and c.
The input is terminated by n=m=0.
Output
One integer in one line represents the maximum number of mission that can be completed.
Sample Input
2 2 1 1 1 2 2 2 0 0
Sample Output
1
ac代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
#define M 10010
int dp[M];
struct misson{
int x,y,t;
}aa[M];
bool cmp(misson a,misson b){
return a.t<b.t;
}
int main(){
//freopen("1.txt","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m),n,m){
for(int i=0;i<m;++i){
scanf("%d%d%d",&aa[i].t,&aa[i].x,&aa[i].y);
dp[i]=1;
}
sort(aa,aa+m,cmp);
int max=0;
for(int j=0;j<m;++j){
for(int i=j-1;i>=0;--i){
if(abs(aa[i].x-aa[j].x)+abs(aa[i].y-aa[j].y)<=aa[j].t-aa[i].t){
if(dp[j]<dp[i]+1)
dp[j]=dp[i]+1;
}
}
if(max<dp[j])
max=dp[j];
}
printf("%d\n",max);
}
return 0;
}