洛谷P2279 消防局的设立 [HNOI2003] 贪心
正解:贪心
解题报告:
这题贪心得挺显然的,,,?居然能有蓝,,,是蓝题太水了嘛,,,?
简单说下,这题一看到就能想到,对最低的没被覆盖到的点给它的祖父建一个消防局
没了?
哦这题实现还挺有趣的感觉
最简单的实现就是用个dfs或堆什么的走一波
然后比较高级的一个是边读边贪心?一个是不用贪心强行dp?到时候具体写下实现趴QAQ
over
边读边贪心就很简单啊,,,因为读一下题目可以知道它读入的是fa[i],所以可以在读入的时候直接处理出deep顺便排个序,然后就直接做了,就可以不要用堆
这个还是挺简单我放下代码就好QwQ
#include<bits/stdc++.h> using namespace std; #define ll int #define mp make_pair #define rp(i,x,y) for(register ll i=x;i<=y;++i) const ll N=1000+10; struct nod{ll dep,nm;nod(){dep=0;}}tr[N]; ll fa[N]={0,1},jl[N],as,n; inline ll read() { register char ch=getchar();register ll x=0;register bool y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar(); if(ch=='-')ch=getchar(),y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar(); return y?x:-x; } inline bool cmp(nod gd,nod gs){return gd.dep>gs.dep;} int main() { n=read();fa[1]=1;tr[1].nm=1;rp(i,2,n)fa[i]=read(),tr[i].dep=tr[fa[i]].dep+1,tr[i].nm=i;sort(tr+1,tr+n+1,cmp);rp(i,0,n)jl[i]=n+1; rp(i,1,n) { ll nw=tr[i].nm,fat=fa[nw],grdfa=fa[fat],grdgrdfa=fa[grdfa],grdgrdgrdfa=fa[grdgrdfa]; jl[nw]=min(jl[nw],min(jl[fat]+1,jl[grdfa]+2)); if(jl[nw]>2)++as,jl[grdfa]=0,jl[grdgrdfa]=min(jl[grdgrdfa],1),jl[grdgrdgrdfa]=min(jl[grdgrdgrdfa],2); } printf("%d\n",as); return 0; }
还有个dp的我还没学TT
顺便,这题有个加强版,将军令,思想差不多我就不写题解了_(:з」∠)_