树形DP例题

忘是亡心i 2023-06-19 06:47 2阅读 0赞

# 树形DP例题 #

DP感觉还是有点陌生，但是这个必须要强化，这类题型实在是太常见了

--------------------

## 一、[题目链接：hdu 1520：Anniversary party][hdu 1520_Anniversary party] ##

--------------------

一道比较经典的树形DP入门题。。。。  
**设dp数组  
dp\[root\]\[0\]表示对于该节点不选  
dp\[root\]\[1\]表示对于该节点选**  
则有：

dp[root][0]+=max(dp[son][0],dp[son][1]);
    dp[root][1]+=dp[son][0];

主要可分为三个部分  
**一、建树，直接用STL中vector即可  
二、树的遍历，dfs  
三、dp**

#include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<vector>
    #define INF 0x3f3f3f3f
    #define ll long long 
    using namespace std;
    int n;
    int dp[6010][5];           //dp[root][1]表示参加宴会,dp[root][0]表示不参加宴会
    int value[6010];
    int father[6010];
    vector<int> tree[6010];
    void dfs(int root){
        
        dp[root][0]=0;
        dp[root][1]=value[root];
        for(int i=0;i<tree[root].size();i++){
        
            int son=tree[root][i];
            dfs(son);
            dp[root][0]+=max(dp[son][0],dp[son][1]);
            dp[root][1]+=dp[son][0];
        }
    }
    int main(){
        
        while(~scanf("%d",&n)){
        
            for(int i=1;i<=n;i++){
        
                scanf("%d",&value[i]);
                father[i]=-1;
                tree[i].clear();
            }
            int a,b;
            while(~scanf("%d%d",&a,&b)){
        
                if(a==0&&b==0)
                    break;
                tree[b].push_back(a);
                father[a]=b;
            }
            int root=1;
            //找到根节点
            for(int i=1;i<=n;i++){
        
                if(father[i]==-1){
        
                    root=i;
                }
            }
            //cout<<root<<endl;
            dfs(root);
            cout<<max(dp[root][1],dp[root][0])<<endl;
        }
        return 0;
    }

--------------------

## 二、[题目链接：洛谷 P1040 加分二叉树][P1040] ##

--------------------

其实感觉这题虽是一个树形结构，但是实际上也是可以用区间DP来求解的  
开始实在没想到，就连那么简单的前序遍历数的递归都卡了一会

#include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<vector>
    #define INF 0x3f3f3f3f
    #define ll long long 
    using namespace std;
    int n;
    int flag;             //防止最后一个数后面出现空格           
    ll dp[35][35];             //dp数组
    int root[35][35];         //存放根节点
    ll search(int l,int r){
        
        ll now;             //存放当前根节点所对应的最大加分值
        if(l>r)
            return 1;
        if(dp[l][r]==-1){
        
            for(int k=l;k<=r;k++){
        
                now=search(l,k-1)*search(k+1,r)+dp[k][k];
                if(now>dp[l][r]){
        
                    dp[l][r]=now;
                    root[l][r]=k;
                }
            }
        }
        return dp[l][r];
    }
    void preoder(int l,int r){
        
        if(l>r)
            return ;
        if(flag==0){
        
            flag=1;
        }
        else{
        
            cout<<' ';
        }
        cout<<root[l][r];
        preoder(l,root[l][r]-1);
        preoder(root[l][r]+1,r);
    }
    int main(){
        
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
        
            for(int j=i;j<=n;j++){
        
                dp[i][j]=-1;
            }
        }
        for(int i=1;i<=n;i++){
        
            scanf("%lld",&dp[i][i]);
            root[i][i]=i;
        }
        ll ans=search(1,n);
        printf("%lld\n",ans);
        preoder(1,n);
        cout<<endl;
        return 0;
    }

[hdu 1520_Anniversary party]: http://acm.hdu.edu.cn/showproblem.php?pid=1520
[P1040]: https://www.luogu.com.cn/problem/P1040