思路
树形DP
算法设计
dfs遍历, 如果子树根节点放置, 则子节点选择是否放置情况中的较小值; 如果子树根节点不放置, 子节点需要放置
f[node][0]+=f[sub_node][1]
f[node][1]+=min(f[sub_node][0], f[sub_node][1])
c++
#include <bits/stdc++.h>
using namespace std;
const int N=1505;
int n;
vector<int> G[N];
bool st[N];
int f[N][2];
void dfs(int node){
f[node][1]=1;
f[node][0]=0;
for(auto v: G[node]){
dfs(v);
f[node][0]+=f[v][1]; // 如果不选择当前node, 需要选择子节点
f[node][1]+=min(f[v][0], f[v][1]); // 如果选择了当前node, 在子节点选择min(f[v][1], f[v][0])
}
}
int main(){
while(cin>>n){
memset(st, 0x00, sizeof st);
memset(f, 0x00, sizeof f);
for(int i=0; i<N; ++i) G[i].clear();
for(int i=0; i<n; ++i){
int node, edges;
scanf("%d:(%d)", &node, &edges);
while(edges--){
int _node;
cin>>_node;
G[node].push_back(_node);
st[_node]=true;
}
}
// 定位根节点
int root=0;
while(st[root]) root++;
dfs(root);
cout<<min(f[root][1], f[root][0])<<endl;
}
return 0;
}
python
from typing import List
import sys
sys.setrecursionlimit(2048)
class Solution:
def main(self, n:int, root:int, G:List[List[int]]):
f=[[0, 0] for _ in range(n)]
def dfs(node):
f[node][0], f[node][1]=0, 1
for v in G[node]:
dfs(v)
f[node][0]+=f[v][1]
f[node][1]+=min(f[v][1], f[v][0])
dfs(root)
print(min(f[root][0], f[root][1]))
if __name__ == '__main__':
sol=Solution()
while True:
try:
n=int(input())
G=[[] for _ in range(n+1)]
vis=[0 for _ in range(n+1)]
for _ in range(n):
node=-1
for item in input().split():
if item.endswith(')'): node = int(item.split(':')[0])
else:
G[node].append(int(item))
vis[int(item)]+=1
root=0
while vis[root]: root+=1
sol.main(n, root, G)
except EOFError:
break