树形DP简介

基本概念

树形DP就是在“树”的数据结构上做动态规划,通过有限次地遍历树,记录相关信息,以求解问题。树形DP有根到叶(常见)叶到根两个方向,就是将父亲结点的信息向下传递给子结点,或者从子结点向上传递信息给父亲结点。

因为树本身至少就有“子结构”性质(树和子树);也本身就具有递归性。所以在树上DP其实是其所当然的事,相比线性动态规划来讲,转移方程更直观,更易理解。


例题 HDU 1520

题意

有n个人,接下来n行是n个人的价值,再接下来n行给出l,k,说的是l的上司是k。要求l与k不能同时出现,求最大的结点价值和。


思路

dp[rt][1]+=dp[G[rt][i]][0];
dp[rt][0]+=max(dp[G[rt][i]][1],dp[G[rt][i]][0]);
//G[rt][i]为当前根节点可以到达的孩子

此类题目的关键在于建树,建树的方法也有多种: 可以用链式结构,可以用下面代码示例中的二维动态数组(相当于链表) 也可以用链式向前星(优化空间,以我目前的经验是比vector稍快),但没有普通的邻接表好写 有的题目甚至不需要建树,只需边遍历边递推

建好树又有了转移方程,其他的就不怕不怕了


代码示例

#include<bits/stdc++.h>
using namespace std;

int n;
const int maxn=6005;

/*
struct Edge{
    int from,to;
}edges[maxn];
*/

vector<int> G[maxn];

int value[maxn];
int father[maxn];
int dp[maxn][2];

void dfs(int rt){
    if(!G[rt].size()){
        dp[rt][1]=value[rt];
        dp[rt][0]=0;
        return ;//边界
    }
    dp[rt][0]=0;
    dp[rt][1]=value[rt];
    for(int i=0;i<G[rt].size();++i){
        dfs(G[rt][i]);
        dp[rt][1]+=dp[G[rt][i]][0];
        dp[rt][0]+=max(dp[G[rt][i]][1],dp[G[rt][i]][0]);
    }
    return ;
}

void init()
{
    memset(value,0,sizeof(value));
    memset(father,0,sizeof(father));
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;++i){
        G[i].clear();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        init();
        for(int i=1;i<=n;++i){
            cin>>value[i];
        }
        int u,v;
        while(cin>>u>>v&&(u+v))
        {
            father[u]=v;
            G[v].push_back(u);
        }
        int root=1;
        while(father[root]){
            root=father[root];
        }
        dfs(root);
        cout<<max(dp[root][0],dp[root][1])<<endl;
    }
    return 0;
}




评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)