【算法与数据结构】——树形DP（1）

刺骨的言语ヽ痛彻心扉 2022-09-04 05:48 38阅读 0赞

# 简介 #

在树形结构上实现的动态规划叫做树形DP。动态规划自身是多阶段决策问题，而树形结构有明显的层次性，正好对应动态规划的多个阶段。树形DP的求解过程一般为自底向上，将子树从小到大作为DP的“阶段”，将节点编号作为DP状态的第1维，代表以该节点为根的子树。树形DP一般采用深度优先遍历，递归求解每棵子树，回溯时从子节点向上进行状态转移。在当前节点的所有子树都求解完毕后，才可以求解当前节点。

# 别墅派对 #

题目地址[HDU2412 别墅派对][HDU2412]  
题意：邀请员工聚会，除了大老板每个人都有一个唯一的老板（直接上司），当一个人被邀请时他的老板不会被邀请，请确定邀请客人的最大数量。另外，需要表明客人列表中的人是否是唯一确定的。  
思路：本题属于最大独立集问题，和POJ2342/HDU1520类似，但增加了唯一性判断。  
AC代码：

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int maxn = 205;
    struct Edge{ 
        int to;
        int next;
    };
    int head[maxn];
    Edge e[maxn];
    int dp[maxn][2];//dp[u][0]表示不选择节点u时的最大员工数，dp[u][1]表示选择节点u时的最大员工数
    int f[maxn][2];//f[u][0]表示不选择节点u时的方案唯一性，等于1则唯一，f[u][1]表示选择节点时的方案唯一性
    map<string,int>ms;
    int cnt;
    void init(int n)
    { 
        for(int i = 1;i <= n;i++)
        { 
            dp[i][0] = 0;
            dp[i][1] = 1;
        }
        memset(f,1,sizeof(f));
        ms.clear();
        cnt = 0;
    }
    void createMap(int n)//有向图建图
    { 
    	for(int i = 1;i <= n;i++)
    	{ 
    		head[i] = -1;
    	}
    	memset(e,0,sizeof(e));
    	string a, b;
    	cin >> a;
    
    	ms[a] = ++cnt;
    	for(int i = 1;i <= n - 1;i++)
    	{ 
    	    cin >> a >> b;
    		if(!ms.count(a))
            { 
                ms[a] = ++cnt;
            }
            if(!ms.count(b))
            { 
                ms[b] = ++cnt;
            }
    		e[i].to = ms[a];
    		e[i].next = head[ms[b]];
    		head[ms[b]] = i;
    	}
    }
    void DFS(int n)
    { 
        for(int u = head[n];u!=-1;u = e[u].next)
        { 
            int v = e[u].to;
            DFS(v);
            if(dp[v][0]>dp[v][1])
            { 
                dp[n][0]+=dp[v][0];
                if(!f[v][0])
                { 
                    f[n][0] = 0;
                }
            }
            else if(dp[v][0]<dp[v][1])
            { 
                dp[n][0]+=dp[v][1];
                if(!f[v][1])
                { 
                    f[n][0] = 0;
                }
            }
            else
            { 
                dp[n][0] += dp[v][0];
                f[n][0] = 0;
            }
            dp[n][1]+=dp[v][0];
            if(!f[v][0])
            { 
                f[n][1] = 0;
            }
        }
    }
    int main()
    { 
        int n;
        while(scanf("%d",&n)&&n)
        { 
            init(n);
            createMap(n);
            DFS(1);
            dp[0][0] = max(dp[1][0],dp[1][1]);
            if(dp[1][0]>dp[1][1])
            { 
                if(!f[1][0])
                { 
                    f[0][0] = 0;
                }
            }
            else if(dp[1][1]>dp[1][0])
            { 
                if(!f[1][1])
                { 
                    f[0][0] = 0;
                }
            }
            if(dp[1][0]==dp[1][1])
            { 
                f[0][0] = 0;
            }
            if(f[0][0])
            { 
                printf("%d Yes\n",dp[0][0]);
            }
            else
            { 
                printf("%d No\n",dp[0][0]);
            }
        }
        return 0;
    }

# 战略游戏 #

题目地址[POJ1463][]  
题意：要放置士兵，看守城市道路，一个士兵可以看守所有与士兵所在节点相连的道路，问最少纺织多少士兵。  
思路：跟上面的别墅派对基本一样

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N=1505;
    vector<int> tree[N];
    int dp[N][2];//dp[u][0]表示不在u点放置士兵最少放置士兵的数量，dp[u][1]表示在u点放置士兵最少放置士兵的数量
    void init()
    { 
        for(int i = 0;i < N;i++)
        { 
            tree[i].clear();
        }
    }
    void DFS(int n)
    { 
        dp[n][0] = 0;
        dp[n][1] = 1;
        for(int i = 0;i < tree[n].size();i++)
        { 
            int v = tree[n][i];
            DFS(v);
            dp[n][1] += min(dp[v][0],dp[v][1]);
            dp[n][0] += dp[v][1];
        }
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int t;
        while(scanf("%d",&t)!=EOF)
        { 
            int a, b,root = -1;
            init();
            for(int j = 1;j <= t;j++)
            { 
                scanf("%d:(%d)",&a,&b);
                if(root == -1)
                { 
                    root = a;
                }
                for(int i = 1;i<=b;i++)
                { 
                    int x;
                    scanf("%d",&x);
                    tree[a].push_back(x);
                }
            }
            DFS(root);
            printf("%d\n",min(dp[root][0],dp[root][1]));
        }
        return 0;
    }

# 工人请愿书 #

题目地址[UVA12186][]  
没找到原网址链接，只能贴一个Vjudge网站的链接了。  
题意：给出一个树状关系图，公司里只有一个老板编号为0，其他人员从1开始编号。除了老板，每个人都有一个直接上司，没有下属的员工成为工人。  
工人们想写一份加工资的请愿书，只有当不少于员工的所有下属的T%人递交请愿书后，该员工才会将请愿书递交给他的直接上级。输出能递交到老板处，最少需要多少工人写请愿书  
思路：树形动态规划  
代码:

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1e5+5;
    vector<int> tree[N];
    int dp[N];//dp[i]表示要第i号老板递交请愿书所需要的最少人数
    bool comp(int a,int b)
    { 
        return dp[a] < dp[b];
    }
    void DFS(int n, int b)
    { 
        dp[n] = 0;
        if(!tree[n].empty())
        { 
            for(int i = 0;i < tree[n].size();i++)
            { 
                DFS(tree[n][i],b);
            }
            int m = ceil(int(tree[n].size())*b*1.0/100);
            sort(tree[n].begin(),tree[n].end(),comp);
            for(int i = 0;i < m;i++)
            { 
                dp[n] += dp[tree[n][i]];
            }
        }
        else
        { 
            dp[n]=1;
        }
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int a, b;
        while(scanf("%d%d",&a,&b)&&a)
        { 
            for(int i = 1;i <= a;i++)
            { 
                int x;
                scanf("%d",&x);
                tree[x].push_back(i);
            }
            DFS(0,b);
            printf("%d\n",dp[0]);
            for(int i = 0;i < N;i++)
            { 
                tree[i].clear();
            }
        }
        return 0;
    }

# 完美的服务 #

题目地址[POJ3398][]  
题意：有n台计算机，由n-1条通信链连接到一起（形成无根树），服务器可以为所有与它相邻的计算机提供服务。若每台客户机（非服务器）都只由一台服务器提供服务，则网络中的一组服务器就形成了完美服务，形成完美服务的最小服务器书叫做完美服务数。给出一个无根树，问最小服务器数。  
思路：这个题目思路跟前面大致相同，但是有一点细节。  
前面都是分为两种情况，这里要分为三种情况。

> dp\[i\]\[0\]表示i为服务器时，他的子节点可以是服务器，也可以不是服务器。  
> dp\[i\]\[1\]表示i不是服务器时，他的父节点是服务器，他的子节点都不能是服务器。  
> dp\[i\]\[2\]表示i不是服务器时，他的父节点不是服务器，则他的子节点中只能有一个是服务器。

前面两种情况都较为简单，关键是最后这一种只能选一个子节点作为服务器，要选哪一个能够保证服务器数量最小。如果直接遍历挑出最小的服务器数量，时间复杂度为O( n 2 n^2 n2)。由于我们前面求出了所有子节点都不是服务器的最小数量，我们可以将其中一个子节点替换成他是服务器的情况，也就是(dp\[u\]\[1\]-dp\[v\]\[2\]+dp\[v\]\[0\])，如此依赖只需要遍历一次取最小值即可，时间复杂度O(n)。  
AC代码：

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1e4+4;
    vector<int> vi[N];
    int dp[N][3];//dp[u][0]表示u为服务器，dp[u][1]表示u不是服务器但它的父节点是，dp[u][2]表示u不是服务器，父节点也不是服务器
    
    void solve(int n,int fa)
    { 
        dp[n][0] = 1;
        dp[n][1] = 0;
        dp[n][2] = 1e6;
        if(vi[n].size()==1&&fa!=0)
        { 
            return;
        }
        for(int i = 0;i < vi[n].size();i++)
        { 
            int u = vi[n][i];
            if(u != fa)
            { 
                solve(u,n);
                dp[n][0]+=min(dp[u][0],dp[u][1]);
                dp[n][1]+=dp[u][2];
            }
        }
        for(int i = 0;i < vi[n].size();i++)
        { 
            int u = vi[n][i];
            if(u!=fa)
            { 
                dp[n][2]=min(dp[n][2],dp[n][1]-dp[u][2]+dp[u][0]);
            }
        }
    }
    int main()
    { 
        int n;
        scanf("%d",&n);
        while(n!=-1)
        { 
            for(int i = 1;i < n;i++)
            { 
                int x,y;
                scanf("%d%d",&x,&y);
                vi[x].push_back(y);
                vi[y].push_back(x);
            }
            solve(1,0);
            printf("%d\n",min(dp[1][0],dp[1][2]));
            for(int i = 1;i <= n;i++)
            { 
                vi[i].clear();
            }
            scanf("%d",&n);
            if(n==0)
            { 
                scanf("%d",&n);
            }
        }
        return 0;
    }

[HDU2412]: https://acm.hdu.edu.cn/showproblem.php?pid=2412
[POJ1463]: http://poj.org/problem?id=1463
[UVA12186]: https://vjudge.net/problem/UVA-12186
[POJ3398]: http://poj.org/problem?id=3398