P2285 [HNOI2004] 打鼹鼠 · znzryb

## 题目大意

给定若干次“鼹鼠出现”的信息：每次出现的时间 $T_i$ 与坐标 $(X_i, Y_i)$。初始在某个位置，每次可以在单位时间内移动一定距离（等价于曼哈顿距离不超过时间差）。问最多能打到多少只鼹鼠。

## AC代码

思路见洛谷进阶篇P227

注释也算写的比较详细

```cpp
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll M=1e4+10;
ll n,m,T[M],X[M],Y[M],dp[M],ans;
// dp存打了第i只鼹鼠的情况下，之前能打多少只鼹鼠(包括这第i只鼹鼠)
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>T[i]>>X[i]>>Y[i];

    }
    for(int i=1;i<=m;i++) {
        ll t=T[i],x=X[i],y=Y[i];
        dp[i]=1;
        for(int j=i-1;j>=1;j--) {
            if(t-T[j]==0) // 时间相同自然不可能状态转移
                continue;
            if(abs(x-X[j])+abs(y-Y[j])<=t-T[j]) //状态转移条件是曼哈顿距离小于时间差
                dp[i]=max(dp[i],dp[j]+1);
        }
    }
    for(int i=1;i<=m;i++) {
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}
// AC https://www.luogu.com.cn/record/183675211
```

## 心路历程（WA，TLE，MLE……）