acwing 1077 皇宫看守

题面

题解(树形DP+状态机模型)

此题与战略游戏的区别 : 战略游戏是有关边的，每个节点选或者不选，因为要求每条边至少有一个点，所以可以通过父节点来维护出子节点选或者不选，但是这个题是点之间的关系，不能通过父节点来维护出子节点的之间的关系，举个例子，图中2号节点不选，那么对于战略游戏这道题来说，可以确定它的儿子5号点就必须选，但是此题，2号节点不选，5号节点也可以不选，因为5号节点可以通过选8号节点来看到，2号节点可以通过选1号节点来看到

f[i][0] : 在点 i 不摆放警卫，且被父结点看到的所有摆放方案的最小花费

f[i][1] : 在点 i 不摆放警卫，且被子结点看到的所有摆放方案的最小花费

f[i][2] : 在点 i 摆放警卫的所有方案的最小花费

f[i] [0] : i 点不摆放，i 可以通过它的父节点来看到，那么它的儿子就要通过自己摆放或者是儿子的儿子节点所看到 ，f[i] [0] += min( f[son][1],f[son][2]) （枚举所有儿子）

f[i][2] : i点摆放 ，那么它的儿子可以通过父节点i ，自己，儿子看到，f[i] [0] += min( f[son][0],f[son][1],f[son][2]) （所有儿子）

f[i][1] :i 点不摆放，i可以通过它的儿子节点所看到，那么就要枚举是哪个儿子放了警卫，假设是第k 个 ，f[i][1] = f[k][2] + min(f[son][1],f[son][2]) (除k以为其他儿子)，我们可以发现，除k以为其他儿子的最小花费和就是 f[i][0]-min(f[k][1],f[k][2])

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=1510;

int n;
int h[N],e[N],ne[N],w[N],idx;
bool is[N];  //标记是否是根节点
int f[N][3];


void add(int a,int b) {
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}


void dfs(int u) {

	f[u][2]= w[u];
	for(int i=h[u]; i!=-1; i=ne[i]) {
		int j=e[i];
		dfs(j);
		f[u][0]+= min(f[j][1],f[j][2]);
		f[u][2]+= min(min(f[j][0],f[j][1]),f[j][2]);
	}

	f[u][1]=1e9;
	for(int i=h[u]; i!=-1; i=ne[i]) {
		int j=e[i];
		f[u][1]=min(f[u][1],f[j][2]+f[u][0]-min(f[j][1],f[j][2]));
	}



}

int main() {

	memset(h,-1,sizeof h);

	cin>>n;
	for(int i=1; i<=n; i++) {
		int id,x,cnt;
		cin>>id>>x>>cnt;
		w[id]=x;
		while(cnt--) {
			int son;
			cin>>son;
			add(id,son);
			is[son]=true;
		}
	}

	int root = 1;
	while(is[root]) root++;

	dfs(root);

	//根节点没有父节点
	cout<<min(f[root][1],f[root][2])<<endl;

	return 0;
}