51 nod 1378 夹克老爷的愤怒 树形dp + 贪心

本文主要是介绍51 nod 1378 夹克老爷的愤怒 树形dp + 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1378 夹克老爷的愤怒

夹克老爷逢三抽一之后，由于采用了新师爷的策略，乡民们叫苦不堪，开始组织起来暴力抗租。

夹克老爷很愤怒，他决定派家丁常驻村中进行镇压。

诺德县有N个村庄，编号0 至 N-1，这些村庄之间用N - 1条道路连接起来。

家丁都是经过系统训练的暴力机器，每名家丁可以被派驻在一个村庄，并镇压当前村庄以及距离该村庄不超过K段道路的村庄。

夹克老爷一贯奉行最小成本最大利润的原则，请问要实现对全部村庄的武力控制，夹克老爷需要派出最少多少名家丁?

Input

第1行：2个数N, K中间用空格分隔(1<= N <= 100000, 0 <= K <= N)。

之后N-1行：每行2个数S, E中间用空格分隔，表示编号为S的村庄同编号为E的村庄之间有道路相连。(0 <= S, E < N)。

Output

输出一个数说明要实现对全部村庄的武力控制，夹克老爷需要派出最少多少名家丁?

Input示例

Output示例

C++的运行时限为：1000 ms ，空间限制为：131072 KB

 题解：不得不说真是一道贪心+树形dp的好题、经典题。对于任意一个节点，如果在其放一个家丁，那么可以控制孩子、祖先、兄弟。既然是多方向，那么肯定只能考虑一个方向，又因为是dfs所以自能自下往上更行，对于方家丁，可以在2k的中点放一个，也就是每隔2k的距离放一个的贪心思想。其实本道题的难点一是k，而是方家丁的节点还可以影响兄弟节点。那么用dp【i】表示i好节点为根的子树能控制i以上包括兄弟的距离，说白了就是能输出的贡献，当dp【i】为负数时表示需要其他子树输出的贡献。注意dfs中的几个if。

总结：在本题中一个节点可以控制祖先、孩子、兄弟，也就是没有先后之分了，只有子树与子树之间的关系。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define inf 10000000
#define N 300000
using namespace std;
int n,k;
int last[N<<1],to[N<<1],head[N],cnt=0;
int ans=0,dp[N];
void ins(int u,int v){last[++cnt]=head[u];head[u]=cnt;to[cnt]=v;
}
void dfs(int x,int fa)
{int minn=inf,maxx=-inf;int i=head[x];while(i){if(to[i]==fa){i=last[i];continue;}dfs(to[i],x);minn=min(minn,dp[to[i]]);maxx=max(maxx,dp[to[i]]);i=last[i];}if(minn==inf) dp[x]=-1;else if(minn<=-k) ans++,dp[x]=k;else if( (maxx+minn)>0 ) dp[x]=maxx-1;else dp[x]=minn-1;
}
int main()
{int u,v;scanf("%d%d",&n,&k);for(int i=1;i<n;i++){scanf("%d%d",&u,&v);u++;v++;ins(u,v);ins(v,u);}if(!k){printf("%d",n);return 0;}dfs(1,0);if(dp[1]<0) ans++;printf("%d",ans);return 0;
}

这篇关于51 nod 1378 夹克老爷的愤怒 树形dp + 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---