uva 1220 - Party at Hali-Bula 【入门树形dp】

Dear 丶 2022-08-13 11:43 310阅读 0赞

题目：uva 1220 - Party at Hali-Bula

题意：一个公司员工要举行聚会，要求任意一个人不能和他的直接上司同时到场，一个员工只有一个支系上司，现在求最多有多少人到场，并且方案是否唯一

分析：分析发现是要求一个树的最大独立集。这里可以用树形dp解决。

定义dp【x】【0】：表示在 i 点不选 i 点的以 x 为子树的最大独立集 而dp【x】【1】 表示x到场的最大独立集

定义f 【x】【0】：表示以x为根且x点不选的子树是否唯一 ，f【x】【1】表示以x为根且x选的子树是否唯一

状态转移方程：dp \[ x \] \[ 1 \] + = dp \[ child \] \[ 0 \] ;

dp \[ x \] \[ 0 \] + = max ( dp \[ child \] \[ 0 \] , dp \[ child \] \[ 1 \] );

而判断唯一性的方程一样的。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <map>
    using namespace std;
    #define maxn 65540
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 300;
    
    vector<int> child[N];
    map<string,int> v;
    int dp[N][3];
    bool f[N][3]; //唯一性
    void DFS(int u)
    {
        if(child[u].size()==0)
        {
            dp[u][0]=0;
            dp[u][1]=1;
            return;
        }
        int size=child[u].size();
        for(int i=0;i<size;i++)
        {
            DFS(child[u][i]);
            if(f[child[u][i]][0])
                f[u][1]=1;
            dp[u][1]+=dp[child[u][i]][0];
            if(dp[child[u][i]][0]>dp[child[u][i]][1])
            {
                dp[u][0]+=dp[child[u][i]][0];
                if(f[child[u][i]][0])
                    f[u][0]=1;
            }
            else
            {
                dp[u][0]+=dp[child[u][i]][1];
                if(dp[child[u][i]][1]==dp[child[u][i]][0]||f[child[u][i]][1])
                    f[u][0]=1;
            }
        }
        dp[u][1]++;
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n) && n)
        {
            memset(dp,0,sizeof(dp));
            memset(f,0,sizeof(f));
            int top = 1;
            string s1,s2;
            cin>>s1;
            v[s1] = top++;
            for(int i=1;i<n;i++)
            {
                cin>>s1>>s2;
                if(!v[s1])
                    v[s1]=top++;
                if(!v[s2])
                    v[s2]=top++;
                child[v[s2]].push_back(v[s1]);
            }
            DFS(1);
            if(dp[1][1]==dp[1][0])
                printf("%d No\n",dp[1][1]);
            else if(dp[1][1]>dp[1][0])
                printf("%d %s\n",dp[1][1],f[1][1]?"No":"Yes");
            else
                printf("%d %s\n",dp[1][0],f[1][0]?"No":"Yes");
            for(int i = 1;i<=n;i++)
                child[i].clear();
            v.clear();
        }
        return 0;
    }

uva

<table style="font-size:13px; width:899px; margin-bottom:0.5em; color:rgb(68,68,68); font-family:'Trebuchet MS',Verdana,Helvetica,Arial,sans-serif"> 
 <tbody> 
  <tr style="background-color:rgb(234,234,234); border-bottom-width:1px; border-bottom-style:solid; border-bottom-color:rgb(234,234,234); padding:0.2em 0.25em"> 
   <td align="right" style="font-size:13px; border-bottom-width:1px; border-bottom-style:solid; border-bottom-color:rgb(234,234,234); padding:0.2em 0.25em"> <a href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;problem=3338" style="margin:0px; padding:0px; color:rgb(153,0,0); text-decoration:none" rel="nofollow">12186</a></td> 
   <td style="font-size:13px; border-bottom-width:1px; border-bottom-style:solid; border-bottom-color:rgb(234,234,234); padding:0.2em 0.25em"> <a href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;problem=3338" style="margin:0px; padding:0px; color:rgb(153,0,0); text-decoration:none" rel="nofollow">Another Crisis</a>&nbsp;代码</td> 
  </tr> 
 </tbody> 
</table>

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <algorithm>
    using namespace std;
    #define maxn 65540
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 101000;
    
    int fa[N];
    vector<int> child[N];
    int dp[N];
    int n,k;
    void dfs(int x)
    {
        int tmp = child[x].size() * k;
        if(tmp%100==0)
            tmp = tmp/100;
        else
            tmp = tmp/100+1;
        vector<int> pps;
        for(int i=0;i<child[x].size();i++)
        {
            int ff = child[x][i],tt = 0;
            dfs(ff);
            tt = dp[ff] ;
            if(child[ff].size()==0)
                tt++;
            pps.push_back(tt);
        }
        int ans = 0;
        sort(pps.begin(),pps.end());
        for(int i=0;i<tmp;i++)
            ans+=pps[i];
        dp[x] = ans;
        return ;
    }
    int main()
    {
    
        while(~scanf("%d%d",&n,&k) && n+k)
        {
            memset(dp,inf,sizeof(dp));
            for(int i=1;i<=n;i++){
                scanf("%d",&fa[i]);
                child[fa[i]].push_back(i);
            }
            dfs(0);
    //        for(int i=0;i<=n;i++)
    //            printf("CAS：%d %d\n",i,dp[i]);
            printf("%d\n",dp[0]);
            for(int i=0;i<=n;i++)
                child[i].clear();
        }
        return 0;
    }