題目鏈接：點擊查看

題目大意：n個人參加聚會，每個人都不想和老板一起參加，問最多可以有多少個人參加，并且判斷方案唯一性

題目分析：這個類型的題目這已經是第三個了，狀態轉移方程都一模一樣，不過這個題有點不同的地方是需要判斷唯一性，我看到網上有兩種方法，一種是通過狀態轉移的過程中如果發現dp[v][1]==dp[v][0]就設置一個flag為false，即在這個地方就出現了分歧，因為想起來和寫起來都比較容易實現這里就不過多贅述了，我還學到了另一個方法，是利用一個vis數組存儲dp數組轉移而來的時候是否唯一，然后相繼傳遞，具體的詳見注釋，上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=210;map<string,int>mp;vector<int>node[N];int dp[N][2];bool vis[N][2];void dfs(int u) {dp[u][0]=0;dp[u][1]=1;vis[u][1]=vis[u][0]=true;for(int i=0;i<node[u].size();i++){int v=node[u][i];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])//如果相等，則是分歧點，由此傳遞上去的dp[u][0]的唯一性也受到影響vis[u][0]=false;if(dp[v][1]>dp[v][0]&&!vis[v][1])//如果dp[u][0]是由dp[v][1]傳遞上去的，則vis[u][0]與vis[v][1]有關vis[u][0]=false;if(dp[v][0]>dp[v][1]&&!vis[v][0])//如果dp[u][0]是由dp[v][0]傳遞上去的，則vis[u][0]與vis[v][0]有關vis[u][0]=false;if(!vis[v][0])//因為dp[u][1]只能由dp[v][0]傳遞而來，所以vis[u][1]只與vis[v][0]有關vis[u][1]=false;} }int main() { // freopen("input.txt","r",stdin);int n;int cnt;while(scanf("%d",&n)!=EOF&&n){for(int i=1;i<=n;i++)node[i].clear();cnt=1;mp.clear();string root;cin>>root;mp[root]=cnt++;for(int i=1;i<n;i++){string u,v;cin>>v>>u;if(!mp[u])mp[u]=cnt++;if(!mp[v])mp[v]=cnt++;node[mp[u]].push_back(mp[v]);}dfs(1);cout<<max(dp[mp[root]][1],dp[mp[root]][0])<<' ';bool flag=true;if(dp[mp[root]][1]>dp[mp[root]][0]&&!vis[mp[root]][1])flag=false;if(dp[mp[root]][1]<dp[mp[root]][0]&&!vis[mp[root]][0])flag=false;if(dp[mp[root]][1]==dp[mp[root]][0])flag=false;if(flag)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0; }

?

總結

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

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