我们用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\n",ans); return 0; }
原文：http://www.cnblogs.com/BLADEVIL/p/3561843.html