| Time Limit: 2000MS | Memory Limit: 10000K | |
| Total Submissions: 7490 | Accepted: 3483 |
Description
Input
Output
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
Source
dp[node][1]+=min(dp[tree[node][i]][0],dp[tree[node][i]][1]); 然后+1
一开始写成 dp[node][1]+=dp[tree[node][i]][0];
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 #define Max 1506 7 int dp[Max][2],fa[Max],tree[Max][12]; 8 int n; 9 int num[Max]; 10 void tree_dp(int node) 11 { 12 int i; 13 for(i=0;i<num[node];i++) 14 { 15 tree_dp(tree[node][i]); 16 dp[node][0]+=dp[tree[node][i]][1]; 17 dp[node][1]+=min(dp[tree[node][i]][0],dp[tree[node][i]][1]); 18 } 19 dp[node][1]++; 20 return; 21 } 22 int main() 23 { 24 int i,j; 25 int a,b; 26 int k,root,f; 27 freopen("in.txt","r",stdin); 28 while(scanf("%d",&n)!=EOF) 29 { 30 memset(dp,0,sizeof(dp)); 31 memset(tree,0,sizeof(tree)); 32 for(i=0;i<Max;i++) 33 fa[i]=-1; 34 for(i=0;i<n;i++) 35 { 36 scanf("%d%*c%*c%d%*c",&f,&k); 37 num[f]=k; 38 for(j=0;j<k;j++) 39 { 40 scanf("%d",&tree[f][j]); 41 fa[tree[f][j]]=f; 42 } 43 } 44 root=0; 45 while(fa[root]!=-1) 46 root=fa[root]; 47 tree_dp(root); 48 printf("%d\n",min(dp[root][0],dp[root][1])); 49 } 50 return 0; 51 }
原文：http://www.cnblogs.com/a1225234/p/5228449.html