poj3342Party at Hali-Bula（树形dp）-白红宇

poj3342Party at Hali-Bula（树形dp）

阅读量：6925 次

发布时间：2019-06-27

本文共 1452 字，大约阅读时间需要 4 分钟。

1 /* 2    树形dp！ 3    判重思路： 4    当dp[v][0]==dp[v][1]时，很自然，flag[u][0]必然是有两种方案的。flag[u][1]则不然， 5    因为它只和dp[v][0]有关系。而若flag[v][0]不唯一时，则必然flag[u][1]也不唯一 6    也就是u的子节点有dp[v][1]==dp[v][0](选与不选都一样)，那么父节点u不选的时候一定会有 7    多种方案！也就是flag[u][0]=false; 否则如果flag[v][0]==flase（子节点不选的时候有多种方案）, 8    那么父节点u选择的时候一定有多种方案，则flag[u][1]=false; 9 */10 #include
     
      11 #include
      
       12 #include
       
        13 #include
        
         14 #include
         15 #include
          
           16 #define N 20517 using namespace std;18 19 map
           
            mp;20 int n;21 int cnt;22 int g[N][N];23 int dp[N][2];24 bool flag[N][2];25 map
            
             ::iterator it;26 27 void dfs(int u){28 for(int v=1; v<=n; ++v)29 if(g[u][v]){30 dfs(v);31 dp[u][1]+=dp[v][0];32 dp[u][0]+=max(dp[v][1], dp[v][0]);33 if(dp[v][1]==dp[v][0]) flag[u][0]=false;34 if(flag[v][0]==false) flag[u][1]=false;35 } 36 }37 38 int main(){39 string na1, na2;40 while(scanf("%d", &n) && n){41 mp.clear();42 memset(g, 0, sizeof(g));43 cnt=0;44 cin>>na1;45 mp[na1]=++cnt;46 for(int i=1; i
             
              >na1>>na2;51 it=mp.find(na1);52 if(it==mp.end())53 mp[na1]=++cnt;54 it=mp.find(na2);55 if(it==mp.end())56 mp[na2]=++cnt;57 g[mp[na2]][mp[na1]]=1; 58 }59 dp[n][1]=1;60 dp[n][0]=0;61 flag[n][1]=flag[n][0]=true;62 dfs(1); 63 if(dp[1][1]>dp[1][0] && flag[1][1]) printf("%d %s\n", dp[1][1], "Yes");64 else if(dp[1][0]>dp[1][1] && flag[1][0]) printf("%d %s\n", dp[1][0], "Yes");65 else printf("%d %s\n", max(dp[1][0], dp[1][1]), "No");66 }67 return 0;68 }