2008-07-29
21:24
设F[I]表示邀请I的最大值
设G[I]表示不邀请I的最大值
F[I] = ∑{G[I.sons]}
G[I] = ∑{Max(F[I.sons],G[I.sons]}}
第一次写Tree DP,写得比较恶心.因为一个下标写错,查了N久才找出错误.
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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | #include <iostream> #include <string> #define msize 300 using namespace std; struct node { string name; int staff[msize]; //staff[0]存储有多少个下属 }guest[msize]; int n; string s1,s2; int cnt; //一共有多少个不同的guest int f[msize][2]; bool status[msize][2]; int dp(int i,bool flag); //flag==true表示选i，flag==false表示不选i int main() { while (cin>>n) { if (n==0) break; cin>>guest[0].name; guest[0].staff[0]=0; cnt=1; for (int i=1;i<n;i++) { cin>>s1>>s2; int j,k; for (j=0;j<cnt;j++) if (guest[j].name==s2) break; if (j==cnt) { guest[cnt].name=s2; guest[cnt++].staff[0]=0; } for (k=0;k<cnt;k++) if (guest[k].name==s1) break; if (k==cnt) { guest[cnt].name=s1; guest[cnt++].staff[0]=0; } guest[j].staff[0]++; guest[j].staff[guest[j].staff[0]]=k; } memset(f,-1,sizeof(f)); memset(status,false,sizeof(status)); int a=dp(0,true); int b=dp(0,false); cout<<max(a,b)<<" "; if (a==b) cout<<"No"<<endl; else if (a>b) { if (status[0][true]) cout<<"No"<<endl; else cout<<"Yes"<<endl; } else { if (status[0][false]) cout<<"No"<<endl; else cout<<"Yes"<<endl; } } return 0; } int dp(int n,bool flag) //flag==true表示选i，flag==false表示不选i { if (f[n][flag]!=-1) return f[n][flag]; //if (guest[n].staff[0]==0) return flag; int sum; if (flag) { sum=0; for (int i=1;i<=guest[n].staff[0];i++) { int idx=guest[n].staff[i]; sum += dp(idx,false); status[n][flag] |= status[idx][false]; } f[n][flag]=sum+1; } else { sum=0; for (int i=1;i<=guest[n].staff[0];i++) { int idx=guest[n].staff[i]; int a=dp(idx,true),b=dp(idx,false); if (a==b) status[n][flag]=true; else if (a>b) status[n][flag] |= status[idx][true]; else status[n][flag] |= status[idx][false]; sum += max(a,b); } f[n][flag]=sum; } return f[n][flag]; } |