题目链接


我开始想到棋盘问题。。。三维数组爆空间。。。 然后就看了看算法标签 想了个一维dp $f\[i\]$表示前i个地鼠最多能被砸死几个,因为发现时间是按顺序排列的,所以可以想到从当前时间前面探出头的地鼠转移,所以 - $f\[i\]=max(f\[i\],f\[j\]+1)(a\[j\].t

    #include<bits/stdc++.h>
    using namespace std;

    int f[10009],n,m;
    struct node{
        int t,x,y;
    }a[10009];

    int dis(int i,int j){
        return abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
    }

    int main(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>a[i].t>>a[i].x>>a[i].y;
            f[i]=1;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=i-1;j++){
                if(dis(i,j)<=abs(a[i].t-a[j].t)){
                    f[i]=max(f[i],f[j]+1);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=m;i++){
            ans=max(ans,f[i]);
        }
        cout<<ans;
        return 0;
    }
Last modification:March 14th, 2020 at 08:50 pm