小胖守皇宫（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