Codeforces Global Round 11 C. The Hard Work of Paparazzi（巧妙的暴力）

C. The Hard Work of Paparazzi
题意：r,n代表一个r * r的矩阵，n代表有n个金币，初始时间是0，现在你站在(1,1)位置，然后给出n个金币出现的位置(x,y)和出现的时间t，这个金币只在t这一分钟出现，过了t就消失，然后保证给出的t是严格递增的，求你能获得的最大收益。每分钟你能向四周移动一个单位。
思路：dp状态很好想，但是转移感觉怎么二维偏序都没法搞，后来听了题解的思路才知道原来这是个暴力，而且t是严格递增的是个很巧妙的条件。r<=500，因此在一个点经过1000分钟，就可以到达这个r * r矩阵的任何一点，所以当遍历到dp[i]时，就可以暴力往前找dp[j]，使得第j个金币出现的时间大于等于t[i]-1000,然后在t递增的条件下，这样的j顶多1000个，然后就暴力跑1000次找最大值，然后对于出现时间小于t[i]-1000的就可以任选了，因为1000分钟可以从任何地方到任何地方，所以维护个前缀最大值即可，然后复杂度就是2rn，即为1e8.

#include<iostream>
#include<cstdio>
using namespace std;
const int MAX_N=101000;
const int INF=0x3f3f3f3f;
int dp[MAX_N];
int t[MAX_N];
struct skt{
    int x,y;
}a[MAX_N];
int Maxl[MAX_N];
int main(void){
    int r,n,i,j;
    scanf("%d%d",&r,&n);
    for(i=1;i<=n;i++)
    scanf("%d%d%d",&t[i],&a[i].x,&a[i].y);
    t[0]=0,a[0].x=1,a[0].y=1;
    for(i=1;i<=n;i++)
    dp[i]=-INF;
    int ans=0;
    for(i=1;i<=n;i++){
        int maxl=-INF;
        int x=lower_bound(t,t+n+1,t[i]-1000)-t;
        if(x)
        maxl=max(maxl,Maxl[x-1]);
        for(j=x;j<i;j++){
            if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)<=t[i]-t[j])
            maxl=max(maxl,dp[j]);
        }
        if(maxl!=-INF)
        dp[i]=maxl+1;
        ans=max(ans,dp[i]);
        Maxl[i]=max(Maxl[i-1],dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}