ACM - nowcoder [HNOI2004]打鼹鼠 - dp

题目链接

题意：中文题自己看

分析：
（这个题最扯淡的是m的值是1e4，然后最暴力的 m^2 的 dp 能过）
非常非常非常类似：最大不上升（下降）子序列。
初始 dp[?] = 1
然后往前看，如果位置 j 的数比位置 i 的数满足题意的条件，那么 dp 值更新。

本题一样
因为机器人的初始位置可控：等价于，我们只需要管过程中的位置和终点位置，起点无所谓。
意味着，对于当前 i，我们枚举之前的每一个 j，如果能到，那么就尝试 dp 更新。

能到 = 在给定的时间走到给定的位置。

代码。

#include<bits/stdc++.h>
using namespace std;

const int maxm = 1e5 + 20;
int t[maxm];
int x[maxm];
int y[maxm];
int dp[maxm];
int n,m;

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
        scanf("%d%d%d", &t[i], &x[i], &y[i]);
    memset(dp, 0, sizeof(dp));
    int ans = 0;
    for(int i = 1; i <= m; i++){
        dp[i] = 1;
        for(int j = 1; j <= i-1; j++)
            if (t[i] - t[j] >= abs(x[i] - x[j]) + abs(y[i] - y[j]))
                dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}