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

题意

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

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

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

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

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

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

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

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;
}