C. The Hard Work of Paparazzi（最长上升子序列)

https://codeforces.com/problemset/problem/1427/C

---

思路:

暴力转移O(n^2)

abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j] i<j 时dp[i]=max(dp[i],dp[j]+1)

但是观察到图最大只有500*500.其最大的曼哈顿距离只有1000

那么假设单调递增的人每次都相隔1，最多1000次，前面的人肯定都能到了。

所以对于前面的，保证到达，没有必要再扫。直接处理一个最值的前缀O1.

对于后面的最多扫1000次获得答案

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e6+100;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL dp[maxn],mx[maxn];
LL t[maxn],x[maxn],y[maxn];
int main(void){
   cin.tie(0);std::ios::sync_with_stdio(false);
   LL r,n;cin>>r>>n;
   memset(dp,-0x3f,sizeof(dp));
   for(LL i=1;i<=n;i++){
       cin>>t[i]>>x[i]>>y[i];
   }
   dp[0]=0;
   x[0]=y[0]=1;///保证能从起点到目标点
   LL ans=0;
   for(LL i=1;i<=n;i++){
       if(i>=2*r) dp[i]=max(dp[i],mx[i-(2*r)]+1);
       for(LL j=max((LL)0,i-2*r);j<=i-1;j++){
           if(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]){
              dp[i]=max(dp[i],dp[j]+1);
           }
       }
       mx[i]=max(mx[i-1],dp[i]);
       ///cout<<"dp["<<i<<"]="<<dp[i]<<"\n";
   }
   for(LL i=1;i<=n;i++) ans=max(ans,dp[i]);
   cout<<ans<<"\n";
   return 0;
}