http://blog.sina.com.cn/s/blog_48f85e1d0100qd3k.html
这个是dfs中用dp,当前点状态取决于其子节点的状态,具体转换如下:
i,0表示以i为根的子树被覆盖,i点未放置的最小数目
i,1表示以i为根的子树被覆盖,i点放置的最小数目
i,2表示i的子树被覆盖,i点未被覆盖的最小数目
之所以有这三种状态,是因为,一个点被覆盖的方式有三种:该点被放置,该点的子节点放置,该点的父节点放置
i,0 =sigm(min(j,0;j,1;j,2)且保证至少一个j,1被取到
i,1 =sigm(min(j,0;j,1;j,2)
i,2 =sigmj,0
#include "stdio.h"
#include "string.h"
#inc......
阅读全文