题意:
给你一个n*n的矩阵,矩阵中有m个区域,每个区域都有走过时间的要求,输入m行每行三个数t,x,y,表示走过x,y的时间必须为第t秒,求最多走过少的区域
直接暴力dp就可以了,但是用g++就过了,c++tle,而且之前没用cmath函数,自己写了一个abs函数,但是超时了,该过之后就A了,3000多ms
yf说是天上掉馅饼的二维形式,恩确实如此
#include"stdio.h" #include"string.h" #include"algorithm" #include"cmath" #define N 10001 using namespace std; struct node { int t,x,y; }A[N]; int cmp(node a,node b){return a.t<b.t;} int max(int a,int b){return a>b?a:b;} int main() { int n,m; int dp[N]; int i,j,ans; while(scanf("%d%d",&n,&m)!=-1&&(n+m)) { for(i=0;i<m;i++) scanf("%d%d%d",&A[i].t,&A[i].x,&A[i].y); sort(A,A+m,cmp); ans=0; for(i=0;i<m;i++) { dp[i]=1; for(j=0;j<i;j++) { if(abs(A[i].t-A[j].t)>=(abs(A[i].x-A[j].x)+abs(A[i].y-A[j].y))) dp[i]=max(dp[i],dp[j]+1); } if(dp[i]>ans)ans=dp[i]; } printf("%d\n",ans); } return 0; }