/*樹形dp！判重思路：當dp[v][0]==dp[v][1]時，很自然，flag[u][0]必然是有兩種方案的。flag[u][1]則不然，因為它只和dp[v][0]有關系。而若flag[v][0]不唯一時，則必然flag[u][1]也不唯一也就是u的子節點有dp[v][1]==dp[v][0](選與不選都一樣)，那么父節點u不選的時候一定會有多種方案！也就是flag[u][0]=false; 否則如果flag[v][0]==flase（子節點不選的時候有多種方案）,那么父節點u選擇的時候一定有多種方案，則flag[u][1]=false; */ #include<iostream> #include<cstring> #include<cstdio> #include<string> #include<map> #include<algorithm> #define N 205 using namespace std;map<string, int>mp; int n; int cnt; int g[N][N]; int dp[N][2]; bool flag[N][2]; map<string, int>::iterator it;void dfs(int u){for(int v=1; v<=n; ++v)if(g[u][v]){dfs(v);dp[u][1]+=dp[v][0];dp[u][0]+=max(dp[v][1], dp[v][0]);if(dp[v][1]==dp[v][0]) flag[u][0]=false;if(flag[v][0]==false) flag[u][1]=false;} }int main(){string na1, na2;while(scanf("%d", &n) && n){mp.clear();memset(g, 0, sizeof(g));cnt=0;cin>>na1;mp[na1]=++cnt;for(int i=1; i<n; ++i){dp[i][1]=1;dp[i][0]=0;flag[i][1]=flag[i][0]=true;cin>>na1>>na2;it=mp.find(na1);if(it==mp.end())mp[na1]=++cnt;it=mp.find(na2);if(it==mp.end())mp[na2]=++cnt;g[mp[na2]][mp[na1]]=1; }dp[n][1]=1;dp[n][0]=0;flag[n][1]=flag[n][0]=true;dfs(1); if(dp[1][1]>dp[1][0] && flag[1][1]) printf("%d %s\n", dp[1][1], "Yes");else if(dp[1][0]>dp[1][1] && flag[1][0]) printf("%d %s\n", dp[1][0], "Yes");else printf("%d %s\n", max(dp[1][0], dp[1][1]), "No");}return 0; }

總結

以上是生活随笔為你收集整理的poj3342Party at Hali-Bula（树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。