皇宫看守

Description

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

Input

帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

Output

输入文件中数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0对于一个n（0 < n<=1500）个结点的树，结点标号在1到n之间，且标号不重复。

Sample Input

输出文件仅包含一个数，为所求的最少的经费。

Sample Output

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

Hint

25

解题思路

我们先设一个f数组
1:f[i][1]为当前i节点放守卫，需要的最小费用
2:f[i][2]为当前i节点不放守卫，被它的子节点监视
3:f[i][3]为当前i节点不放守卫，被它的父亲监视

首先考虑1
如果它当前点放守卫，那么它的子节点就可以不放或者放守卫

f[x][1]+=min(f[a[i].to][1],min(f[a[i].to][2],f[a[i].to][3]));

再考虑2
如果当前点不放守卫，被它儿子监视，那么就要找它最小的儿子

for(int i=head[x];i;i=a[i].next)
	 o+=min(f[a[i].to][1],f[a[i].to][2]);
	f[x][2]=2147483647;
	for(int i=head[x];i;i=a[i].next)
	 f[x][2]=min(f[x][2],o-min(f[a[i].to][1],f[a[i].to][2])+f[a[i].to][1]);

最后考虑3
如果当前点不放守卫，被它父亲监视，那么它的儿子的儿子的点要放守卫，来监视它儿子

f[x][3]+=f[a[i].to][2];

最后就迎来我们的AC代码

AC代码

#include<cstdio>
#include<iostream>
using namespace std;
long long n,k,tot,b[1000005],c[1000005],head[1000005],f[100005][4];
struct node
{
   
	long long to, next;
}a[1000005];
void add(long long x,long long y)//邻接表
{
   
	a[++tot]=(node){
   y, head[x]};
	head[x]=tot;
}
void dp(long long x)//dp
{
   
	for(int i=head[x];i;i=a[i].next)
	{
   
		dp(a[i].to);//递归
		f[x][1]+=min(f[a[i].to][1],min(f[a[i].to][2],f[a[i].to][3]));//1
		f[x][3]+=f[a[i].to][2]; //3
	}
	f[x][1]+=b[x];//累加
	long long o=0;
	for(int i=head[x];i;i=a[i].next)
	 o+=min(f[a[i].to][1],f[a[i].to][2]);//找最小
	f[x][2]=2147483647;//初值
	for(int i=head[x];i;i=a[i].next)
	 f[x][2]=min(f[x][2],o-min(f[a[i].to][1],f[a[i].to][2])+f[a[i].to][1]);//2
}
int main()
{
   
	scanf("%lld",&n);
	for(long long i=1;i<=n;i++)//输入
	{
   
		long long x;
		scanf("%lld",&x);
		scanf("%lld",&b[x]);
		scanf("%lld",&k);
		for(long long j=1;j<=k;j++)
		{
   
			long long y;
			scanf("%lld",&y);
			add(x,y);//有向
			c[y]++;//y点有父亲
		} 
	}
	for(int i=1;i<=n;i++)
	 if(c[i]==0)//如果为根
	 {
   
		dp(i);
		printf("%lld",min(f[i][1],f[i][2]));
		break;
	 }
}

谢谢