[HNOI2004]打鼹鼠 解题报告

本文主要是介绍[HNOI2004]打鼹鼠 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题一上来就想到了是$O(M^2)$的DP，但是没有想到优化，导致跑得比较慢。
当然其实对于这个题而言优化有无是无所谓的，但是这个优化的思想还是很好的。
我一开始是想得用前面的去更新后面的，而如果我们反着来想的话，就可以发现一个优化了。
设$f_i$表示最后到i可以取得的最大数量，那么显然有方程

$$f_i=max \{ f_j+1,1\le j<i \ |\ |x_i-x_j|+|y_i-y_j|\le t_j-t_i \}$$ 这时假如我们从大到小枚举j，那么显然存在更小的j使得i被更新的必要条件是存在更小的j使得 $f_j+1>f_i$，也就是说只要我们搞个前缀最大值就可以剪枝了。
当然，这实际上并不能在减弱其最坏时间复杂度，（我们只需要让第一个点time=1，而剩下所有点都time=2就可以做到这点了。）但对于随机数据来说则能提高100倍左右，效果是惊人的；因为直观上来看，随下标的递增，f数组是趋向于越来越大的。
通过这道题，让我们看到了前/后缀Max在剪枝中的重要应用，我们在暴搜和卡常数的时候一定要想着他。
代码（朴素版）：

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int x[10005],y[10005],t[10005];
int f[10005];
int main(){freopen("mouse.in","r",stdin);freopen("mouse.out","w",stdout);int n,m,ans=0,i,j;scanf("%d%d",&n,&m);for(i=0;i<m;++i)scanf("%d%d%d",t+i,x+i,y+i),f[i]=1;for(i=0;i<m;++i){for(j=i;++j<m;)if(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[j]-t[i])f[j]=max(f[j],f[i]+1);ans=max(ans,f[i]);}printf("%d\n",ans);
}

代码（剪枝版）：

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int x[10005],y[10005],t[10005];
int f[10005],b[10005];
inline int in(){char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';return x;
}
int main(){freopen("mouse.in","r",stdin);freopen("mouse.out","w",stdout);int n,m,ans=0,i,j;n=in(),m=in();for(i=1;i<=m;++i)t[i]=in(),x[i]=in(),y[i]=in(),f[i]=1;for(i=1;i<=m;++i){for(j=i-1;b[j]+1>f[i];--j)if(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])f[i]=max(f[i],f[j]+1);b[i]=max(f[i],b[i-1]);}printf("%d\n",b[m]);
}

这篇关于[HNOI2004]打鼹鼠 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---