(Luogu) P2279 [HNOI2003]消防局的设立

本文主要是介绍(Luogu) P2279 [HNOI2003]消防局的设立，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

解题思路：此题可以树形dp也可以贪心过，看了第一篇题解，非常nice！贪心的策略也很好想，我们从深度最大的开始，他没有孩子孙子，我们自然选择去建立他的祖父，这样可以覆盖到更多的点，我们如何去判断点是否已经被覆盖到了呢，可以开一个o数组 o[i]表示 i到最近的消防站的距离 初始化为 0x3f3f3f3f 。代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e3+5;
int n,a[maxn],f[maxn],d[maxn],o[maxn],ans;
bool cmp(int x,int y) {return d[x]>d[y]; //按深度从大到小排序
}
int main() {std::ios::sync_with_stdio(0);cin>>n;a[1]=1,o[1]=inf;for(int i=2; i<=n; ++i) {cin>>f[i];d[i]=d[f[i]]+1,a[i]=i,o[i]=inf;}sort(a+1,a+n+1,cmp);for(int i=1; i<=n; ++i) {int np=a[i],fa=f[np],gfa=f[fa];o[np]=min(o[np],min(o[fa]+1,o[gfa]+2));if(o[np]>2) {ans++;o[gfa]=0;o[f[gfa]]=min(o[f[gfa]],1);o[f[f[gfa]]]=min(o[f[f[gfa]]],2);}}cout<<ans<<endl;return 0;
}

 

这篇关于(Luogu) P2279 [HNOI2003]消防局的设立的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---