題意：公司里n個人，要舉辦一場party，但是到場的人不能碰到他的直隸上司，問最多能到場多少人。

思路：樹形dp，就是求在樹上的最大獨立集合，加唯一性特判。dp(u，0)表示不選u點的條件最大人數，kp是唯一與否。狀態轉移有兩套

選u點dp（u,1)=sum（dp（v,0））

不選u點 dp（u,0）=sum（max（dp（v,1），dp（v,0）））；

code：

#include <bits/stdc++.h> using namespace std;#define ft(i,s,t) for (int i=s;i<=t;i++) #define frt(i,t,s) for (int i=t;i>=s;i--) #define cls(v,c) memset(v,c,sizeof(v)) const int INF=0x3f3f3f3f; const int N=205;int dp[N][2],kp[N][2],len,n; vector<int>v[N]; string s1,s2,s; map<string,int>mp;void dfs(int u) {dp[u][0]=0;dp[u][1]=1;kp[u][0]=kp[u][1]=1;for (int i=0;i<v[u].size();i++){int t=v[u][i];dfs(t);dp[u][0]+=max(dp[t][0],dp[t][1]);dp[u][1]+=dp[t][0];if (dp[t][0]>dp[t][1]&&dp[t][0]==0) kp[u][0]=0;else if (dp[t][1]>dp[t][0]&&dp[t][1]==0) kp[u][0]=0;else if (dp[t][1]==dp[t][0]) kp[u][0]=0;if (kp[t][0]==0) kp[u][1]=0;}} int main() {while (~scanf("%d",&n)&&n){ft(i,0,n) v[i].clear();cls(dp,0);cls(kp,0);mp.clear();len=1;cin>>s;mp[s]=len++;ft(i,1,n-1){cin>>s1>>s2;if (mp.count(s1)==0) mp[s1]=len++;if (mp.count(s2)==0) mp[s2]=len++;v[mp[s2]].push_back(mp[s1]);}dfs(1);if (dp[1][0]>dp[1][1]&&kp[1][0]) printf("%d Yes\n",dp[1][0]);else if (dp[1][1]>dp[1][0]&&kp[1][1]) printf("%d Yes\n",dp[1][1]);else printf("%d No\n",max(dp[1][0],dp[1][1]));} }

總結

以上是生活随笔為你收集整理的uva 1220——Party at Hali-Bula的全部內容，希望文章能夠幫你解決所遇到的問題。

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