CodeForces - 1427C - The Hard Work of Paparazzi dp

題意：給出n個點 ( x i , y i ) (x_i,y_i) (xi​,yi​)，如果主人公在 t i t_i ti​在這個點上，就可以拍照，從一個點到另一個點的花費時間是兩點的曼哈頓距離。

想不出來 又是抄的題解

dp狀态: d p [ i ] dp[i] dp[i]表示 [ 1 , i ] [1,i] [1,i]個點最多可以拍多少照片

初始化: d p [ 0 ] = 0 , d p [ i ] = dp[0]=0,dp[i]= dp[0]=0,dp[i]=負無窮

思路：(假設 i < j i<j i<j)

如果曼哈頓距離 ∣ x i − x j ∣ + ∣ y i − y j ∣ ≤ t i − t j |x_i-x_j|+|y_i-y_j| \leq t_i-t_j ∣xi​−xj​∣+∣yi​−yj​∣≤ti​−tj​，就說明從 j j j點到 i i i點拍照是可能的。如果 n 2 n^2 n2暴力dp，顯然不行

根據矩形性質，可以得到 ∣ x i − x j ∣ + ∣ y i − y j ∣ ≤ 2 r |x_i-x_j|+|y_i-y_j| \leq 2r ∣xi​−xj​∣+∣yi​−yj​∣≤2r

當 2 r ≤ t i − t j 2r \leq t_i-t_j 2r≤ti​−tj​時， ∣ x i − x j ∣ + ∣ y i − y j ∣ ≤ 2 r ≤ t i − t j |x_i-x_j|+|y_i-y_j|\leq 2r \leq t_i-t_j ∣xi​−xj​∣+∣yi​−yj​∣≤2r≤ti​−tj​恒成立，滿足這個條件的 i , j i,j i,j可達。

由于 t j < t i t_j<t_i tj​<ti​恒成立，是以 i − j ≤ t i − t j i-j \leq t_i-t_j i−j≤ti​−tj​

将 j j j分為兩段：

• 當 2 r ≤ i − j 2r\leq i-j 2r≤i−j時， ∣ x i − x j ∣ + ∣ y i − y j ∣ ≤ 2 r ≤ i − j ≤ t i − t j |x_i-x_j|+|y_i-y_j|\leq 2r \leq i-j \leq t_i-t_j ∣xi​−xj​∣+∣yi​−yj​∣≤2r≤i−j≤ti​−tj​，對于這些 j < i j<i j<i，與 i i i是可達的，是以可以進行狀态轉移，但是這樣的 j j j顯然有很多個，可以用一個字首數組記錄下最大值，轉移一次即可。
• 當 i − 2 r < j i-2r<j i−2r<j時， ∣ x i − x j ∣ + ∣ y i − y j ∣ ≤ t i − t j |x_i-x_j|+|y_i-y_j| \leq t_i-t_j ∣xi​−xj​∣+∣yi​−yj​∣≤ti​−tj​不一定成立，是以要逐個判斷，但是最多隻有 2 r 2r 2r個 j j j，是以複雜度是 O ( 2 n r ) O(2nr) O(2nr)

代碼：

const int maxn=2e6+7;
const int INF=0x3f3f3f3f;
const ll INFF=1e18;
int r,n,t[maxn],x[maxn],y[maxn],dp[maxn],ans=0,maxx[maxn];
int main()
{
    scanf("%d%d",&r,&n);
    rep(i,1,n)scanf("%d%d%d",&t[i],&x[i],&y[i]),dp[i]=maxx[i]=-INF;
    x[0]=1,y[0]=1;
    dp[0]=maxx[0]=0;
    rep(i,1,n)
    {
        if (i>=2*r)dp[i]=maxx[i-2*r]+1;//j from[0,max(0,i-2r-1)]
        for (int j=i-1;j>=max(0,i-2*r);j--)//j from[max(0,i-2r),i-1]
        {
            if (abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])dp[i]=max(dp[i],dp[j]+1);
        }
        maxx[i]=max(maxx[i-1],dp[i]);
    }
    W(maxx[n]);
    return 0;
}