1. 小游戏（贪心）
题干：
谷同学很喜欢玩计算机游戏，特别是战略游戏，但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题：他必须在一个中世纪的城堡里设防，城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以看到所有边。你能帮助他吗？
你的任务是给出士兵的最少数目。
输入：包含多组数据。每组数据表示一棵树，在每组数据中：
第一行是结点的数目。
接下来的几行，每行按如下格式描述一个结点：结点标识符 : ( 道路的数目 ) 结点标识符1 结点标识符2 ...... 结点标识符道路的数目
或者
结点标识符 : (0)
对于 n (0<n<=1500) 个结点，结点标识符是一个从 0 到 n - 1 的整数。每条边在测试用例中只出现一次。
对于每组数据，各给出一个整数表示士兵的最少数目。
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
代码如下：
这里和小学期的知识对应起来了。（动态规划dp[n][2]的设计）
#include <iostream>
#include <cstring>
using namespace std;const int MAXN = 1505;
int dp[MAXN][2], visited[MAXN], link[MAXN][MAXN];
void DFS(int root)
{visited[root] = 1;for (int i = 0; link[root][i] != -1; ++i){int m = link[root][i];if (!visited[m]){DFS(m);dp[root][1] += dp[m][0];dp[root][0] += min(dp[m][0], dp[m][1]);}}dp[root][0]++;
}
int main()
{int n;while (scanf("%d", &n) != EOF){memset(dp, 0, sizeof(dp));memset(visited, 0, sizeof(visited));memset(link, 0, sizeof(link));int node, next, temp, root;for (int i = 0; i < n; i++){scanf("%d:(%d)", &node, &next);root = (!i) ? node : root;int j = 0;for (; j < next; ++j){cin >> temp;link[node][j] = temp;}link[node][j] = -1;}DFS(root);cout << min(dp[root][0], dp[root][1]) << endl;}return 0;
}