hdu 2412 Party at Hali-Bula【树形dp】

àì夳堔傛蜴生んèń 2021-12-15 04:31 212阅读 0赞

[HDU 2412][]

和[poj 2342（hdu 1520）][poj 2342_hdu 1520]差不多，多了一个判断最优解是(Yes)否(No)唯一。关键问题也在这个判断最优解是否唯一上。

先定义dp\[u\]\[2\],表示选（dp\[\]\[1\]）或不选（dp\[\]\[0\]）当前节点u所获得的最大值。

对于叶子节点 ：dp\[u\]\[0\]=0,dp\[u\]\[1\]=1;

对于非叶子节点：dp\[u\]\[0\]=Σmax(dp\[v\]\[0\],dp\[v\]\[1\])(v是u的儿子节点)

dp\[u\]\[1\]+=Σdp\[j\]\[0\]

最大值答案即为:max(dp\[1\]\[0\],dp\[1\]\[1\])(以1为根节点)。

下面考虑如何判断最优解是否唯一(v是u的儿子节点)：

先定义dup\[u\]\[2\]。dup\[u\]\[0\]表示不选u节点是(dup\[u\]\[0\]=1)否(dup\[u\]\[0\]=0)会有多解,dup\[u\]\[1\]表示选u节点是(dup\[u\]\[0\]=1)否(dup\[u\]\[0\]=0)会有多解。 （本来不想先定义状态，想根据逻辑推出需要这个状态的，但感觉不太好叙述，就这样吧）

如果选v节点比不选v节点优(dp\[v\]\[1\]>dp\[v\]\[0\])而且选v节点时目前最优解不唯一(dup\[v\]\[1\]=1)，那么说明不选u节点时最优解也不唯一(dup\[u\]\[0\]=1)。因为此时v要选所以u就不能选，也就是v要选必须u不能选而且由于选v有多解那么推到u不选就有多解。

其他情况就同理了，比如说不选v节点比选v节点优，那么能推出选u节点会有多解(dup\[u\]\[1\]=1)

而且如果不选v节点有多解(dup\[v\]\[0\]=1)，那么选u节点一定会有多解(dup\[u\]\[1\]=1)。

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<string>
     5 #include<vector>
     6 #include<map>
     7 #include<algorithm>
     8 using namespace std;
     9 const int maxn=206;
    10 map<string,int> mp;
    11 vector<int> tree[maxn];
    12 int dp[maxn][2],dup[maxn][2];
    13 int n;
    14 
    15 void init()
    16 {
    17     memset(dp,0,sizeof(dp));
    18     memset(dup,0,sizeof(dup));
    19     for(int i=0;i<=n;i++) tree[i].clear();
    20     mp.clear();
    21 }
    22 
    23 void dfs(int u,int fa)
    24 {
    25     dp[u][0]=0,dp[u][1]=1;
    26     for(int i=0;i<tree[u].size();i++){
    27         int v=tree[u][i];
    28         if(v==fa) continue;
    29         dfs(v,u);
    30         dp[u][0]+=max(dp[v][0],dp[v][1]);
    31         dp[u][1]+=dp[v][0];
    32         if(dp[v][0]>dp[v][1]&&dup[v][0]) dup[u][0]=1;
    33         else if(dp[v][0]<dp[v][1]&&dup[v][1]) dup[u][0]=1;
    34         else if(dp[v][0]==dp[v][1]) dup[u][0]=1;
    35         if(dup[v][0]) dup[u][1]=1;
    36     }
    37 }
    38 
    39 int main()
    40 {
    41     string s1,s2;
    42     while(cin>>n,n)
    43     {
    44         init();
    45         int t=1;
    46         cin>>s1;
    47         mp[s1]=t;
    48         for(int i=1;i<n;i++){
    49             cin>>s1>>s2;
    50             if(!mp[s1]){t++,mp[s1]=t;}
    51             if(!mp[s2]){t++,mp[s2]=t;}
    52             tree[mp[s2]].push_back(mp[s1]);
    53         }
    54         dfs(1,-1);
    55         if(dp[1][0]>dp[1][1]&&!dup[1][0])
    56             cout<<dp[1][0]<<" Yes"<<endl;
    57         else if(dp[1][0]<dp[1][1]&&!dup[1][1])
    58             cout<<dp[1][1]<<" Yes"<<endl;
    59         else cout<<max(dp[1][0],dp[1][1])<<" No"<<endl;
    60     }
    61     return 0;
    62 }

转载于:https://www.cnblogs.com/zxhyxiao/p/7678134.html

[HDU 2412]: http://acm.split.hdu.edu.cn/showproblem.php?pid=2412
[poj 2342_hdu 1520]: http://www.cnblogs.com/zxhyxiao/p/7580515.html