P2285 [HNOI2004] 打鼹鼠

Koei · 2025-10-08 09:54:28 · 算法·理论

状态：dp_i表示最后打第i只鼠鼠时可以打的最大鼠鼠数量

初始化：dp_i=1打第i只鼠鼠时至少打了第i只鼠鼠

状态转移：dp_i=max(dp_i,dp_p+1)，dp_p表示可以打鼠鼠p时的最大数量

确定答案：max(dp_i)因为不确定最后打死哪只鼠鼠

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e5+10);
int n,m,ans(0);
struct node{
    int t,x,y;
}a[maxn];
int dp[maxn];
bool check(int i,int j){
    return (abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y))<=abs(a[i].t-a[j].t);
} 
int main(){
    cin>>n>>m;
    for(int i(1);i<=m;i++){
        cin>>a[i].t>>a[i].x>>a[i].y;
    }
    for(int i(1);i<=n;i++){
        dp[i]=1;
    }
    for(int i(1);i<=m;i++){
        for(int j(1);j<=i;j++){
            if(i!=j&&check(i,j)){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    for(int i(1);i<=m;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans<<'\n';
    return 0;
}

注意到：

打死一只鼠鼠蹲3年