【每日一题】3月16日[HNOI2004]打鼹鼠

题意

有一个 $n*n$ 的网格然后每过一段时间就会有鼹鼠在网格里探出头我们设计了一个机器人去打这个鼹鼠机器人每个时间单位只能上下左右移动一格求机器人最多打的鼹鼠的个数

这个题目一个看就是 $dp$ 或者贪心事实证明就是一个带着贪心的 $dp$

看起来很难在二维的地图上还有时间但是实际上我们没有必要在二维的地图上去 $dp$

自然我们将机器人放在一个鼹鼠即将出来的地方一定是对的这样一开始机器人一开始就能打到鼹鼠（不一定是第一个鼹鼠出来的地方）

假设我们选择了这一个洞那么我们只要去比较下一个老鼠出来的时候我们能不能赶到

因此我们的转移方程就很简单

$if(两个洞之间的距离<=赶过去的时间)$

$dp[i] = max(dp[i] , dp[j] + 1)$

因为数据读入是按时间顺序的所以我们可以一边读入一边 $dp$

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

struct node{
    int t , x , y;
}a[N];
ll dp[N];

void solve(){
    int n = read() , m = read();
    for(int i = 1 ; i <= m ; ++i){
        dp[i] = 1;
        a[i].t = read() , a[i].x = read() , a[i].y = read();
        for(int j = i - 1 ; j > 0 ; --j){
            if(abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y) <= a[i].t - a[j].t)
                dp[i] = max(dp[i] , dp[j] + 1);
        }
    }
    ll ans = 0;
    for(int i = 1 ; i <= m ; ++i){
        ans = max(ans , dp[i]);
    }
    cout<<ans<<endl;
}

int main(void){
    solve();

    return 0;
}