poj1463-1A

题目大意，有一些节点，节点间有路，节点上放哨兵可以监视和此节点直接连接的节点。求用最少的哨兵，监视所有的节点，没有盲区。。。。

其实一看就知道是一个dp，01背包。每个节点上只有两种情况，放或者不放，按平时来说就是简单的dp，但是这次是一个树，所以要在树上做01背包。

状态方程很好想：
dp【i】【0】表示第i点不放哨兵
dp【i】【1】表示第i点放哨兵
那么我们知道：
dp【i】【0】 = dp【j0】【1】 + dp【j1】【1】 + dp【j2】【1】+dp【j3】【1】。。。。（j1，j2， j3。。 jm为i的孩子，也就是说如果i不放，那么他的孩子必须放）。
dp【i】【1】 = min（dp【j0】【1】， dp【j0】【0】） + min（dp【j1】【1】， dp【j1】【0】）。。。。（j1，j2， j3 。。jm为i的孩子，也就是说如果i放，那么他的孩子必可放可不放，求最小值）。

有了状态方程代码就好些了
如下：
[cpp]
#include<iostream>
using namespace std;

#define nMax 1505
#define inf 0x3ffffff

int son[nMax], brother[nMax];
bool father[nMax];
int dp[nMax][2];
int n;

void dfs(int root)
{
    dp[root][0] = 0;
    dp[root][1] = 1;
    int k = son[root];
    while (k != -1)
    {
        dfs(k);
        dp[root][0] += dp[k][1];//如果不放，孩子必放
        dp[root][1] += min(dp[k][0], dp[k][1]);//如果放，孩子可放可不放，求最小值
        k = brother[k];
    }
}

int main()
{
    while (scanf("%d", &n) != EOF)
    {
        int root;
        memset(son, -1, sizeof(son));
        memset(father, false, sizeof(father));
        int u, vNum, v;
        for (int i = 0; i < n; ++ i)
        {
            scanf("%d:(%d)", &u, &vNum);
            for (int j = 0; j < vNum; ++ j)
            {
                scanf("%d", &v);
                brother[v] = son[u];//同一个父亲节点下的上一个兄弟
                son[u] = v;//u的孩子
                father[v] = true;//判断是否有父亲，求根节点
            }
        }
        for (int i = 0; i < n; ++ i)
        {
            if (!father[i])
            {
                root = i;
                break;
            }
        }
        dfs(root);
        printf("%d\n", dp[root][0] < dp[root][1] ? dp[root][0] : dp[root][1]);
    }
    return 0;
}

补充：软件开发 , C++ ,