Loading... [题目链接](https://www.luogu.org/problemnew/show/P2285 "题目链接") <!--more--> * * * 我开始想到棋盘问题。。。三维数组爆空间。。。 然后就看了看算法标签 想了个一维dp $f\[i\]$表示前i个地鼠最多能被砸死几个，因为发现时间是按顺序排列的，所以可以想到从当前时间前面探出头的地鼠转移，所以 - $f\[i\]=max(f\[i\],f\[j\]+1)(a\[j\].t<a\[i\].t$且$dis(i,j)\\leq tim(i,j))$ 代码： ```cpp #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 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏