小胖守皇宫(Tree dynamic)

问题描述
huyichen世子事件后,xuzhenyi成了皇上特聘的御前一品侍卫。

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

输入格式 Input Format

输入文件中数据表示一棵树,描述如下:
第1行 n,表示树中结点的数目。
第2行至第n+1行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号i(0 对于一个n(0 < n <= 1500)个结点的树,结点标号在1到n之间,且标号不重复。
输出格式 Output Format
输出文件仅包含一个数,为所求的最少的经费。

样例输入 Sample Input
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

样例输出 Sample Output

25

注释 Hint

如图

算法分析
树型动态规划
本题既可以用有向树来做,也可以用无向图随机选根结点

分析可见,对于当前结点i,它有num个子结点,它有它有3种状态:

1:在当前位放置守卫的情况(被自己所控制)
2:不在当前位放置守卫,但是它已经被它的子结点所控制
3:不在当前位放置守卫,它还没有被它的子结点所影响(即被其父结点控制)

用f[i,x]表示结点i的第x种情况:

1情况的值由其子结点的1,2,3情况得到最优
2情况的值由其子结点的1,2情况得到最优
3情况的值只可由其2情况求和.

第2种情况要特别注意,要求它的子结点中必须有一个是1状况的,所以可以先将最小值求和,
然后加上这num个子结点中每个的1情况与最优情况的f值之差–most

方程:
f[i,1]:=Σ(min{f[son[j],1],f[son[j],2],f[son[j],3]})+a[i]
f[i,2]:=Σ(min{f[son[j],1],f[son[j],2]})+most
f[i,3]:=Σ(f[son[j],2]),           1<=j<=num

还有要注意的一点就是对于极限数据,树被拉成了一条链.
有向图解法如果每次递归都开一个数组那么内存会爆,对此,可以不用数组记录子结点,而直接用链表就
可以大大节约空间了.甚至把数组改成全局变量也是可行的,就是注意递归调用要在DP之前.

【代码】

#include 
#define MAXN 1501
#define MAXINT 2000000000
typedef struct
{
        int v, num;
        int child[MAXN];
}node;
 
node a[MAXN];
int f[MAXN][4];
int min2(int x, int y)
{
       return x

小胖守皇宫(Tree dynamic)》上有2条评论

laruence进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注


*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>