題目模型
n×n 網格，m 個任務 `(t, r, c)` 必須在時刻 t 到達 (r,c)。每單位時間可上下左右移動一格或原地。求最多完成任務數。
本質：任務按時間排序，若從任務 i 能趕到任務 j (`t_j - t_i >= |r_i-r_j| + |c_i-c_j|`)，則可轉移。求最長路徑（DAG 上最長路）。
解法：DP + 線段樹優化
- 任務按 `t` 升序排序。
- `dp[i]` = 以任務 i 結尾的最大完成數。
`dp[i] = max(1, max(dp[j]) + 1)` 對所有能轉移到 i 的 j。
- 轉移條件：`t_i - t_j >= |x_i-x_j| + |y_i-y_j|`。
變換坐標 `u = x+y, v = x-y`，條件變為 `t_i - t_j >= max(|u_i-u_j|, |v_i-v_j|)`。
用 2D 線段樹或 CDQ 分治優化最大值查詢。
複雜度
- O(m log^2 m) 或 O(m log m)，m ≤ 10000 可行。
參考題解
acmerblog 詳細講解與代碼
