51nod 1378：夹克老爷的愤怒很好玩的一道树状dp

1378 夹克老爷的愤怒

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

取消关注

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

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

诺德县有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示例

官方题解：树形DP，贪心思想，从叶子节点向上，能不放就不放，到了k长就放一个。

后序遍历，记录不同子树上传的状态，子树状态记录为该子树可以向上管理的（缺少的用负数）

可能A子树放置的家丁可以把B子树的村庄全部覆盖，这样就可以节约家丁数了。

min_length = min(dp[child])

max_length = max(dp[child])

if(min_length <= -K) {

++result;

dp[cur_idx] = K; //子树需要暴力支援深度达到K了，必须在当前位置放置一个家丁，并向上提供K的暴力输出

} else if(max_length + min_length > 0) {

dp[cur_idx] = max_child - 1; //有一个子树放置的家丁能够把全部其他需要镇压的村庄都覆盖

} else {

dp[cur_idx] = min_child - 1; //继续向上级要求暴力支持

}

最后如果root的状态小于0要额外多放一个。

这个题目真的挺好玩的，把这n个村庄n-1个连接想象成是一个树，然后记录每一个节点缺少的级别，当到达了k个级别的时候就要加上一个家丁，此时这个节点缺少的级别是正的k，因为它要开始照顾到它的兄弟子树了。

手动扩栈扩栈也是头一次。。。

代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

#define inf 0x3f3f3f3f

int res;

int n, k;

int s, e;

int used[100050];

int dp[100050];

vector<int>node[100050];

void dfs(int x)

{

	used[x] = 1;

	int minn = inf;

	int maxn = -inf;

	int size = node[x].size();

	int i;

	for (i = 0; i < size; i++)

	{

		int temp = node[x][i];

		if (used[temp] == 0)

		{

			dfs(temp);

			minn = min(minn, dp[temp]);

			maxn = max(maxn, dp[temp]);

		}

	}

	if (minn == inf)

	{

		dp[x] = -1;

	}

	else if(minn<=-k)

	{

		res++;

		dp[x] = k;

	}

	else if (maxn + minn > 0)

	{

		dp[x] = maxn - 1;

	}

	else

	{

		dp[x] = minn - 1;

	}

	used[x] = 0;

}

int main()

{

	//freopen("i.txt", "r", stdin);

	//freopen("o.txt", "w", stdout);

	int i;

	scanf("%d%d", &n, &k);

	for (i = 1; i <= n - 1; i++)

	{

		scanf("%d%d", &s, &e);

		s++;

		e++;

		node[s].push_back(e);

		node[e].push_back(s);

	}

	if (k == 0)

	{

		printf("%d", n);

		return 0;

	}

	dfs(1);

	if (dp[1] < 0)

	{

		res++;

	}

	printf("%d", res);

	//system("pause");

	return 0;

}

巴特西

51nod 1378：夹克老爷的愤怒很好玩的一道树状dp

最新文章

热门文章

巴特西

51nod 1378：夹克老爷的愤怒 很好玩的一道树状dp

最新文章

热门文章

51nod 1378：夹克老爷的愤怒很好玩的一道树状dp