树形DP
用dp[i][0]来表示该点没有放兵，以这个点为根的子树所需的最少兵数。
用dp[i][1]来表示该点有放兵，以这个点为根的子树所需的最少兵数。
那么可以得到状态方程
dp[fa][0]+=dp[son][1];//如果该父亲不放，那么儿子必须放
dp[fa][1]+=min(dp[son][0],dp[son][1]);//如果该父亲放，儿子在放和不放之间选择最小的
访问的时候，因为要先知道儿子的信息，用递归的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define maxn 1600
int dp[maxn][2];
vector<int> ve[maxn];
void solve(int fa){
dp[fa][0] = 0; dp[fa][1]= 1;
int son;
for (int i = 0; i < ve[fa].size(); i++){
son = ve[fa][i];
solve(son);
dp[fa][0] += dp[son][1];
dp[fa][1] += min(dp[son][1],dp[son][0]);
}
}
int main(){
int n;
while (~scanf("%d", &n)){
int u,v,num;
int root = -1;
for (int i = 0; i <= n; i++)
ve[i].clear();
for (int i = 0; i < n; i++){
scanf("%d:(%d)", &u, &num);
if (root == -1) root = u;
for (int j = 0; j < num; j++){
scanf("%d", &v);
ve[u].pb(v);
}
}
solve(root);
printf("%dn", min(dp[root][0],dp[root][1]));
}
return 0;
}
|