[刷题笔记] Luogu P2285 [HNOI2004] 打鼹鼠

Problem

Analysis

我们初始可以任意决定机器人的位置，状态很多，暴力显然会寄掉。

不妨先贪心的思考一下。我们肯定希望机器人初始在最先出现鼹鼠的洞，因为出现在没有鼹鼠的洞是无效的。

题目保证输入数据是严格按照出现时间递增顺序给出。定义 \(f_i\) 表示前 \(i\) 只鼹鼠最多能打到多少个。如果能在时间内从 \(j\) 走到 \(i(\forall j <i)\)，则可以转移，取最大值即可。

我们显然希望同样走到 \(i\) 号鼹鼠能打到的最多。如果没有打到最多，则一定不是最优解。（由于机器人可以任意决定初始位置，所以走到 \(i\) 号鼹鼠默认是满足在打到它的前提下，因为最坏情况就是只打它自己）

转移的时候我们只需要考虑鼹鼠位置之间的转移即可，至于如何行走我们是可以直接求出来的。

至此，我们就把这道题转换成了 二维最长上升子序列模型？。虽然需要判断的条件更多，但其实非常类似。

Code

/*
二维最长不下降子序列模型？

设 $f_i$ 表示前 $i$ 只鼹鼠最大能打到多少。显然我们鼹鼠出现的时间是按照顺序输入的。

每次如果能从 $j$ 走到 $i$ ，也就是能在时间限制内走到鼹鼠，则可以打。取max即可
即 $f_i = max(f_i,f_j+1)$

我们显然期望在前 $i$ 只鼹鼠中能打到尽可能多的，否则下次利用就不是最大的。

同时前 $i$ 只鼹鼠打多少都不影响后面如何打，因为第 $i$ 只鼹鼠出现的时间是固定的。符合无后效性，局部最优解。

显然也避免了重复。

需要注意 $ans = max(f)$ 我们需要在全程取 max ，显然不一定能打到 $n$ ，也不一定打 $n$ 就是 max
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1000100;
int n,m;
struct Node
{
    int t,x,y;
}qwq[N];
int f[N];
int maxn = 0;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>qwq[i].t>>qwq[i].x>>qwq[i].y,f[i] = 1;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<i;j++)
        {
            int lenx = abs(qwq[i].x - qwq[j].x);
            int leny = abs(qwq[i].y - qwq[j].y);
            if(lenx + leny  <= abs(qwq[i].t-qwq[j].t))
            {
                f[i] =max(f[i],f[j]+1);
            }
        }
        maxn = max(maxn,f[i]);
    }
    cout<<maxn<<endl;
    return 0;
}