蓝桥杯备考：动态规划之最长上升子序列打鼹鼠
这道题第一眼想用BFS，但是初始位置不固定，要考虑的太多太多了
我们可以看到time是递增的，我们可以用最长递增子序列来做
一共是这么多个鼹鼠，按照时间排序，依次枚举每个鼹鼠，找出最长上升子序列，就是能打到的老鼠
如果距离小于等于时间差，就能连上
我们还是按动态规划最基本的做法
分析状态表示 f[i]表示以第i个鼹鼠结尾的最长子序列是多大
推导状态转移方程
接下来就按正常的最长上升子序列来做就行了，下面是代码
#include <iostream>
using namespace std;
const int N = 1e4+10;
int n,m;
int t[N],x[N],y[N];
int f[N];
bool check(int i,int j)
{
return abs(t[i]-t[j])>= abs(x[i]-x[j]) * abs(y[i]-y[j]);
}
int main()
{
cin >> n >> m;
for(int i = 1;i<=m;i++)
{
cin >> t[i] >> x[i] >> y[i];
}
int ret = 0;
for(int i = 1;i<=m;i++)
{
f[i] = 1;
for(int j = 1;j<i;j++)
{
if(check(i,j))
{
f[i] = max(f[i],f[j]+1);
}
}
ret = max(ret,f[i]);
}
cout << ret << endl;
return 0;
}