皇宫看守 解题报告

原题

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。
皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状，某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。
可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

题目大意

这道题的题目大意和 战略游戏 很像。
但仔细看看，你会发现多了一个 经费 的条件。
所以题目大意需要稍稍改动一下，就是 ：
求一棵n个节点的树上，在满足两点之间的最大距离不超过2的前提下的最小花费。

解题方法

DFS和二进制就不说了

树上DP

思路

这道题的解题思路也差在这个 经费 上。
其实在 战略游戏 上，每个节点的开销可以 都看作1。
而在这道题中，每个节点的开销是 不同的。
所以这就导致了 每个点被不同点看住 的 开销不同。
所以在这道题需要对 被不同点看住 的情况 分开 ，也就是把 被父节点 和 被子节点 看住 分开。
那么，可以这么设计状态：

• f [ u ] [ 0 ] 表示在以u节点为根节点的子树中，u节点在被父节点看住时所需的最小费用
• f [ u ] [ 1 ] 表示在以u节点为根节点的子树中，u节点在被子节点看住时所需的最小费用
• f [ u ] [ 2 ] 表示在以u节点为根节点的子树中，u节点在自己取时所需的最小费用

然后来看看转移：

• 在状态0下：
  • 从状态0转移：不行 由于当前节点不取，所以在子节点的视角来看，是父节点不取。所以不可行
  • 从状态1转移：可以
  • 从状态2转移：可以
• 在状态1下：
  • 从状态0转移：不行 原因同上。
  • 从状态1转移：可以
  • 从状态2转移：可以 且由于是“子节点看住”，所以必须至少有一个子。
• 在状态2下：
  • 从状态0转移：可以
  • 从状态1转移：可以
  • 从状态2转移：可以

最后，初值……

• \(f\ _{u,\ 0} = 0\)
• \(f\ _{u,\ 1} = INF\)
• \(f\ _{u,\ 2} = k\ _{u}\)
• \(f\ _{leaf,\ 1} = d\ _{leaves}\)
  ……和目标
• \(min\ _{ f\ _{root,\ 1},\ f\ _{root,\ 2} }\)

所以，整个递推式总结如下：

递推式

• 定义

  \(f\ _{u,\ 0}\ \text{表示在以u节点为根节点的子树中，u节点在被父节点看住时所需的最小费用}\)
  \(f\ _{u,\ 1}\ \text{表示在以u节点为根节点的子树中，u节点在被子节点看住时所需的最小费用}\)
  \(f\ _{u,\ 2}\ \text{表示在以u节点为根节点的子树中，u节点在自己取时所需的最小费用}\)

• 转移

  \(f_{u,\ 0}=\Sigma \min\ _{f_{son,\ 1},\ f_{son,\ 2}}\)
  \(f_{u,\ 1}=\min\ _{f_{son,2}\ +\ \Sigma \min\ _{f_{otherson,1},\ f_{otherson,2}}}\)
  \(f_{u,\ 2}=\Sigma \min\ _{f_{son,0},\ f_{son,1},\ f_{son,2}}\)

• 初值

  \(f_{u,\ 0}=0\)
  \(f_{u,\ 1}=\infty\)
  \(f_{u,\ 2}=k\ _{u}\)
  \(f_{leaf,\ 1}=d\ _{leaf}\)

• 终点

  \(min\ _{f_{root,\ 1},\ f_{root,\ 2}}\)

哦，对了，还有一个落下了：

• 时间复杂度

  \(O\ (\ n\ ^2\ )\)

代码

#include <stdio.h>
inline int min ( int x, int y ) { return x < y ? x : y; }
int n, id, k [ 1501 ], m, r, root, f [ 1501 ] [ 3 ], next [ 1501 ], vect [ 1501 ], head [ 1501 ], edgenum;
bool is_leaf [ 1501 ], indeg [ 1501 ];

void addedge ( int u, int v ) {
    edgenum ++;
	vect [ edgenum ] = v;
	next [ edgenum ] = head [ u ];
	head [ u ] = edgenum;
}

void dfs ( int u ) {
	if ( is_leaf [ u ] ) {
		f [ u ] [ 1 ] = f [ u ] [ 2 ] = k [ u ], f [ u ] [ 0 ] = 0;
		return ;
	}
	f [ u ] [ 0 ] = 0, f [ u ] [ 1 ] = 0x7ffffff, f [ u ] [ 2 ] = k [ u ];
	int sum = 0;
	for ( int e = head [ u ]; e; e = next [ e ] ) {
		int v = vect [ e ];
		dfs ( v );
		sum += min ( f [ v ] [ 1 ], f [ v ] [ 2 ] );
	}
	for ( int e = head [ u ]; e; e = next [ e ] ) {
		int v = vect [ e ];
		f [ u ] [ 0 ] += min ( f [ v ] [ 1 ], f [ v ] [ 2 ] );
		f [ u ] [ 1 ] = min ( f [ u ] [ 1 ], ( f [ v ] [ 2 ] < f [ v ] [ 1 ] ) ? ( sum ) : ( sum - f [ v ] [ 1 ] + f [ v ] [ 2 ] ) );
		f [ u ] [ 2 ] += min ( f [ v ] [ 0 ], min ( f [ v ] [ 1 ], f [ v ] [ 2 ] ) );
	}
	
}

int main ( ) {
	scanf ( "%d", & n );
	for ( int i = 1; i <= n; i ++ ) {
		scanf ( "%d", & id ), scanf ( "%d", & k [ id ] ), scanf ( "%d", & m );
		if ( m == 0 ) is_leaf [ id ] = true;
		for ( int j = 1; j <= m; j ++ ) 
           scanf ( "%d", & r ), indeg [ r ] = true, addedge ( id, r );
		
	}
	for ( int i = 1; i <= n; i ++ )
		if ( ! indeg [ i ] ) {
			root = i;
			break;
		}
	dfs ( root );
	printf ( "%d\n", min ( f [ root ] [ 1 ], f [ root ] [ 2 ] ) );
	return 0;
}

总结

做这道题时，关键是要抓住 经费 这个条件，这使得这道题与 战略游戏 不同，再根据子节点/父节点的关系，就能做出该题。

皇宫看守 解题报告

原文：https://www.cnblogs.com/wukaixuan/p/12707165.html