一道小清新动态规划题,直接设 \(dp[i]\) 表示前 \(i\) 个鼹鼠最多能打到几个,然后状态转移方程也很好想了。
参考代码:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,ans,dp[10010],x[10010],y[10010],times[10010];
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
int main()
{
IOS;
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>times[i]>>x[i]>>y[i];
for(int i=1;i<=m;i++)
dp[i]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<i;j++)
if(abs(x[i]-x[j])+abs(y[i]-y[j])<=abs(times[i]-times[j]))
dp[i]=max(dp[i],dp[j]+1);
for(int i=1;i<=m;i++)
ans=max(ans,dp[i]);
cout<<ans;
QwQ;
}