题目描述：
（警卫看守）
给一棵n个结点的树，要求选中最少的结点使得每个结点被自己或直接相联的结点覆盖
树形DP
很明显是一颗树，虽然没有跟结点，但可以随便拎起一个来开始DP
状态表示f[i,0..2];
f[i,0]表示该结点可以被儿子看到的最优解
f[i,1]表示该结点自己放置一个装置来进行覆盖
f[i,2]表示该结点可以被父亲看到的最优解
需要注意的是，f[i,0],f[i,2]都是可以被看到的最优解，而不是说只能被儿子或父亲看到的最优解
那么方程即为
f[i,0]:=min(f[soni,0],f[soni,1]); //不完全
f[i,1]:=min(f[soni,0],f[soni,1],f[soni,2]);
f[i,2]:=min(f[soni,0],f[soni,1]);
其中f[i,0]若全部儿子都取f[soni,0]那就不成立了，所以需要特别处理
还有一些细节
1.第23行只能是小于号不能取等号，因为相等的时候归到下一类应该更优
2.叶子结点f[i,0]需要赋成极大值，影响的是f[fatheri,2]，即它父亲的2状态，如果不赋初值，
也就是f[fatheri,2]是0的话即表示用覆盖fatheri这个结点，它以及其子树所需最小费用为0，
而这样的话相当于在fatheri的father处放置一个结点使得i也能被覆盖，其实是覆盖不到的
而从DP本身考虑，f[i,0]当i是叶子时这个状态不存在，所以也不应该有
3.输出时取min不能有f[1,2]因为该状态不存在，可能存在类似于第2条的问题
View Code 1 program sky; 2 var 3 x,y,i,n : longint; 4 f : array[0..10001,0..2] of longint; 5 a : array[0..10001,0..1000] of longint; 6 v : array[0..10001] of boolean; 7 function min(qq,ww: longint ):longint; 8 begin 9 if qq>ww then exit(ww) ; exit(qq); 10 end; 11 procedure dp(x : longint); 12 var 13 i,mini : longint; 14 vv : boolean; 15 begin 16 vv:=false; mini:=maxlongint>>1; 17 f[x,1]:=1; 18 for i:=1 to a[x,0] do 19 if not v[a[x,i]] then 20 begin 21 v[a[x,i]]:=true; 22 dp(a[x,i]); 23 if f[a[x,i],0]
总结起来，树形dp的定义状态方式一般f[i,xx]都表示以i结点为根的子树的最优解
skysun原创，装载请注明出处 http://www.cnblogs.com/skysun