Strategic game （树形dp）

Strategic game （树形dp）"/>

Strategic game （树形dp）

题目传送门

Description

Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?

Your program should find the minimum number of soldiers that Bob has to put for a given tree.

For example for the tree:

the solution is one soldier ( at the node 1).
Input

The input contains several data sets in text format. Each data set represents a tree with the following description:

the number of nodes
the description of each node in the following format
node_identifier:(number_of_roads) node_identifier1 node_identifier2 … node_identifiernumber_of_roads
or
node_identifier:(0)

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500);the number_of_roads in each line of input will no more than 10. Every edge appears only once in the input data.
Output

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following:
Sample Input

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)
Sample Output

1
2

题意：就是有一个城市，有一些道路，每个士兵站在道理的路口，可以看做节点，可以防守与这个节点相连的道路（边）,问最少安排多少个士兵才能把所有的道路都防守了。

我最近也是决定学习树形dp，这是一道树形dp的入门题，每个节点放一个人可以防守住与他相邻的边，我们设dp[ i ] [ 0]表示以i节点为根，i节点不放士兵时的最优解。那么dp[ i ] [ 1 ]表示以i节点为根，i节点放士兵时的最优解。
那么我们就可以遍历与i相连的所有节点，当第i个节点不放时,j为与他相连的节点，则有：

dp[ i ] [ 0]=dp[ i ] [ 0]+dp[j][1];

当第i个节点放士兵时,j为与他相连的j节点选择放士兵，也可以选择不放士兵，则有：

dp[ i ] [ 0]=dp[ i ] [ 0]+min(dp[j][1],dp[j][0]);

这样我们就从最后dp[ 1 ][ 1 ]和 dp [ 1 ] [ 0 ] 中选出最优解即可

ac代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<cmath>
using namespace std;
typedef  long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+100;
const int MOD=1e4+7;
const double PI=3.1415926535;
int lowbit(int x){return x&-x;}
ll gcd(ll x, ll y){ return y == 0 ? x : gcd(y, x%y); }
ll lcm(ll x, ll y){ return x / gcd(x, y)*y; }
inline ll dpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; }
inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t); b >>= 1; t = (t*t); }return r; }
struct node{int to, nxt;
} edge[maxn];
int head[maxn], n, dp[maxn][2], tol;
void add(int a,int b)//链式前向星存图
{edge[++tol].to = b;edge[tol].nxt = head[a];head[a] = tol;
}
void dfs(int u,int fa)
{for (int i = head[u]; i!=-1;i=edge[i].nxt){int v = edge[i].to;if(v==fa)continue;dfs(v,u);dp[u][0] += dp[v][1];dp[u][1] += min(dp[v][1], dp[v][0]);}
}
int main()
{while(cin>>n&&n){tol = 0;memset(head, -1, sizeof head);memset(dp, 0, sizeof dp);for (int i = 0; i <= n;i++)dp[i][1] = 1, dp[i][0] = 0;for (int i = 1; i <= n;i++){int u, m, v;scanf("%d:(%d)",&u,&m);for(int j=0;j<m;j++){scanf("%d",&v);add(u,v);add(v,u);}}dfs(1,-1);int res = min(dp[1][1], dp[1][0]);cout << res << endl;}//system("pause");return 0;
}

我要学会dp！！！！！！！