本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-09-05 10:22:49

更好的阅读体验

基础的DP各位大佬已经讲得很明白了，本文主要讲一讲优化

DP状态很容易想到：$f[i]$ 表示打完第 $i$ 只鼹鼠能获得的最多数量。

转移：$f[i]=\min\limits_{j<i,\ t[i]-t[j]>=dis(i,j)}f[j]+1$，即对于每一个打完第 $j$ 个能来得及走到第 $i$ 个的 $j$，算最大的 $f[j]+1$。

重点来了！！

优化

我们发现，如果时间差大于 $2\times n$，无论在天涯海角哪里都能走到，又因为输入的时间是升序排列，我们只需要在转移时维护 $g[i]$ 表示 $\max\limits_{j<=i}f[i]$，这样在转移 $f[i]$ 时就可以先用 $start=upper\_bound-1$ 找出最后一个“时间差大于 $2\times n$” 的鼹鼠，他前面的鼹鼠无论多远都能到达，就可以直接用 $g[start]$ 来代替，枚举时就只需要从 $start$ 开始枚举了。

#include<bits\/stdc++.h>
using namespace std;
int t[10010],x[10010],y[10010];
int f[10010],g[10010];
int dis(int a,int b) {
	return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
	for(int i=1;i<=m;i++) {
		int start=max(0,int(upper_bound(t+1,t+i,t[i]-2*n)-t-1));
		f[i]=g[start]+1;
		for(int j=max(1,start);j<i;j++) {
			if(t[i]-t[j]>=dis(i,j))
				f[i]=max(f[i],f[j]+1);
		}
		g[i]=max(g[i-1],f[i]);
	}
	printf("%d\n",g[m]);
    return 0;
}

哎哎哎，别急着走，后面还有：

继续优化

我们发现，由于时间是递增的，所以 $i$ 的 $start$ 一定不会小于 $i-1$ 的 $start$，所以我们用 $start[i]$ 记录第 $i$ 只鼹鼠的 $start$，那么 $upper\_bound$ 时就只需要从 $start[i-1]$ 开始查找。

#include<bits\/stdc++.h>
using namespace std;
int t[10010],x[10010],y[10010];
int f[10010],g[10010],start[10010];
int dis(int a,int b) {
	return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
	for(int i=1;i<=m;i++) {
		start[i]=max(0,int(upper_bound(t+start[i-1],t+i,t[i]-2*n)-t-1));
		f[i]=g[start[i]]+1;
		for(int j=max(1,start[i]);j<i;j++) {
			if(t[i]-t[j]>=dis(i,j))
				f[i]=max(f[i],f[j]+1);
		}
		g[i]=max(g[i-1],f[i]);
	}
	printf("%d\n",g[m]);
	return 0;
}

哎哎哎，别急着走，后面还有：

继续继续优化

我们甚至可以直接不用 $upper\_bound$ 和 $start$ 数组了（没错），开一个变量 $start$，维护当前的 $start$，转移之前用一个

for(;t[i]-t[start+1]>=2*n;start++);

来更新 $start$，可以发现，整个程序运行下来，$start$ 最多只会更新 $n$次，所以复杂度可忽略。

最终代码：

#include<bits\/stdc++.h>
using namespace std;
int t[10010],x[10010],y[10010];
int f[10010],g[10010],start;
int dis(int a,int b) {
	return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
	for(int i=1;i<=m;i++) {
		for(;t[i]-t[start+1]>=2*n;start++);
		f[i]=g[start]+1;
		for(int j=max(1,start);j<i;j++) {
			if(t[i]-t[j]>=dis(i,j))
				f[i]=max(f[i],f[j]+1);
		}
		g[i]=max(g[i-1],f[i]);
	}
	printf("%d\n",g[m]);
	return 0;
}

不开O2可达48ms，可见优化非常显著。

请勿抄袭，如果一定要抄，请理解明白后再抄