题解【[HNOI2004]打鼹鼠 题解】

· · 题解

这道题好像是我 19 年在 ** 机构试听的时候给做的题。woc 我当时连红题都切不稳让我做蓝
现在再看这道题刚开始我只想到了三维状态，看到题解的一维状态恍然大悟 Orz 各路神仙先。
闲话少说，切入正题——

首先这道题我们显然会想到 f_{t,x,y} 表示在 t 这个时间节点中身处 (x,y) 这个地方最多能打多少鼹鼠。
然后我们四连通填表就好惹，但是，这个空间开不下去呀/fad

所以我们要另寻捷径。我们换一种思路，设 f_p 为抓鼹鼠序列以 p 结尾时我们最多能抓多少小鼠。

当我们确定好了状态之后，这道题已经完成了一大半了。我们先枚举 p 作为起点（毕竟起点任意，能抓就抓），那么考虑转移，显然我们可以枚举一个 i 为下一个我们要抓的鼹鼠。

那么怎么判定能抓呢？我们记录不了路径啊，可是由于起点任意，所以我们可以假装在这个鼹鼠的位置，拓展我们又假装在那个鼹鼠的位置。也就是说，我们可以直接枚举一个 i 作为下一个要抓的鼹鼠。

怎么判断能不能抓到呢？我们只要算一算他们的曼哈顿距离（\left| (x_0-x_1)\right|+\left| (y_0 - y_1)\right|）能不能够跑（val_p-val_i） 就可以转移了。

转移方程是什么呢？不难写出来是 f_p = \max(f_p, f_i + 1)。

如何初始化呢？因为我们枚举的 p 作为起点可以抓所以 f_p = 1。

最后的答案可能不一定是 f_m，因为不一定这就是最大的，要从头到尾在枚举一遍才行。

上代码： 

#include <iostream> 
#include <cmath>
#define MAXN 100000
using namespace std;
struct node {
    int x, y, val;
}in[MAXN + 10];
int n, m, f[MAXN + 10], ans = 0;
int max(int x, int y) {return ((x > y) ? (x) : (y));}
int dist(int x, int y, int xx, int yy) {//计算曼哈顿距离
    return abs(x - xx) + abs(y - yy);
}
int main() {
    cin >> n >> m;
    for(int p = 1; p <= m; p++)
        cin >> in[p].val >> in[p].x >> in[p].y;
    for(int p = 1; p <= m; p++) {
        f[p] = 1;
        for(int i = 1; i < p; i++)
            if(dist(in[p].x, in[p].y, in[i].x, in[i].y) <= in[p].val - in[i].val)//是否可以转移
                f[p] = max(f[p], f[i] + 1);
    }   
    for(int p = 1; p <= m; p++)//求最大值
        ans = max(ans, f[p]);
    cout << ans << endl;
}