OI

【动态规划】树形DP

树形DP是一种特殊的DP，利用树形结构的无环、分层、有很好的递归性质的特点，进行状态转移。常用dfs整棵树+记忆化的方式实现。

以下是几道难度递进的例题：

P2015二叉苹果树

由于限制了二叉，约束条件就很简明了：

f[i][j]=max{f[左][k]+f[右][j-k-1]+a[i]}(0<=k<=j-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstring>
using namespace std;
int n,q;
int e[105][105];
int l[105]={0},r[105]={0},w[105];
int f[105][105]={0};
void build(int v){
    int i;
    for(i=1;i<=n;i++)
        if(e[v][i]>=0){
            l[v]=i;
            w[i]=e[v][i];
            e[v][i]=-1;
            e[i][v]=-1;
            build(i);
            break;
        }
    for(i=1;i<=n;i++)
        if(e[v][i]>=0){
            r[v]=i;
            w[i]=e[v][i];
            e[v][i]=-1;
            e[i][v]=-1;
            build(i);
            break;
        }
        
}

int dp(int i,int j){
    if(j==0)return 0;
    if(l[i]==0&&r[i]==0)return w[i];
    if(f[i][j]!=0)return f[i][j];
    for(int k=0;k<=j-1;k++)
        f[i][j]=max(f[i][j],dp(l[i],k)+dp(r[i],j-k-1)+w[i]);
    return f[i][j];
}

int main(){
    
    cin>>n>>q;
    int a,b,c;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            e[i][j]=-1;
    
    for(int i=1;i<=n-1;i++){
        cin>>a>>b>>c;
        e[a][b]=c;
        e[b][a]=c;
    }
    
    build(1);
    
    cout<<dp(1,q+1);
    
    return 0;
}

P2014选课

与上一题不同的是节点的子节点数没有限制了，增加了一个循环，于是也增加了一个维度。转移方程类似背包，不同点就是如果选子节点，父节点一定要选。

设$f_{i,j,k}$为编号为$i$的节点直到第$j$个子节点（第0个为节点$i$本身），取$k$个的最大值
$f_{i,j,k}=max(f_{i,j-1,k},f_{i,j-1,k-t}+f_{ison,s[ison],t}),0<=t<=k-1$

其中$s[i]$为节点$i$的子节点数

$f_{i,j,0}=0$（不选）$f_{i,0,k}=w[i]$（节点本身）

其中必须选根节点的限制体现在最后一维的循环中的-1上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN=305;
int n,m;
int w[MAXN]={0},s[MAXN]={0};
vector<int> g[MAXN];
int f[MAXN][MAXN][MAXN]={0};

int dp(int a,int b,int c){
    if(f[a][b][c]!=-1)return f[a][b][c];
    if(c==0){f[a][b][c]=0;return 0;}
    if(b==0){
        f[a][b][c]=w[a];
        return f[a][b][c];
    }
    
    f[a][b][c]=dp(a,0,c);
    for(int j=0;j<=c-1;j++)
        f[a][b][c]=max(f[a][b][c],
        dp(a,b-1,c-j)+dp(g[a][b-1],s[g[a][b-1]],j));
    return f[a][b][c];
}

int main(){
    memset(f,-1,sizeof(f));
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        g[a].push_back(i);
        s[a]++;
        w[i]=b;
    }
    
    printf("%d\n",dp(0,s[0],m+1));
    
    return 0;
}

P2515软件安装

一开始以为这题和上一题一样，是直接多叉树背包，只是把限制条件节点数改成了花费。然而后来发现图可能有环，这使此题又上了一个难度。
先使用tarjan缩点，一个连通分量中只能全选。这样将图化成一个无环的森林，再将每棵树的根连到超级根节点0，最后在新图树上背包得到答案。

其中必须选根节点的限制体现在最后一维的循环中的-w[i]上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
const int MAXN=105,MAXM=505;
int n,m;
vector<int> g[MAXN],g2[MAXN];
int v[MAXN]={0},w[MAXN]={0};

int s[MAXN]={0},s2[MAXN]={0},
dfn[MAXN]={0},low[MAXN]={0},indx=0;
int color[MAXN]={0},cnt[MAXN]={0},sum=0;
stack<int> st;
bool vis[MAXN]={0};

void tarjan(int u){
    dfn[u]=++indx;
    low[u]=indx;
    vis[u]=1;
    st.push(u);
    for(int i=0;i<s[u];i++){
        int v=g[u][i];
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])
            low[u]=min(low[u],low[v]);
    }
    
    if(dfn[u]==low[u]){
        color[u]=++sum;
        vis[u]=0;
        while(st.top()!=u){
            color[st.top()]=sum;
            vis[st.top()]=0;
            st.pop();
        }
        st.pop();
    }
}

int he[MAXN]={0};
bool del[MAXN]={0};
bool ze[MAXN]={0};
void trans(){
    for(int i=0;i<=n;i++)
        if(dfn[i]==0)tarjan(i);
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<s[i];j++){
            int t=g[i][j];
            if(he[color[i]]==0||he[color[i]]==i)
                he[color[i]]=i;
            else del[i]=1;
            if(color[t]==color[i]){
                if(del[i]){
                    w[he[color[i]]]+=w[i];
                    v[he[color[i]]]+=v[i];
                }
            }
            else{
                g2[he[color[i]]].push_back(t);
                s2[he[color[i]]]++;
            }
        }
        cnt[color[i]]++;
    }
    
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=sum;i++)
        if(cnt[i]>1&&!vis[he[i]]){
            vis[he[i]]=1;
            g2[0].push_back(he[i]);
            s2[0]++;
        }
    
    for(int i=1;i<=n;i++)
        if(ze[i]&&!vis[he[color[i]]]){
            vis[he[color[i]]]=1;
            g2[0].push_back(i);
            s2[0]++;
        }
    
}

int f[MAXN][MAXN][MAXM]={0};
int dp(int a,int b,int c){
    if(del[a])return dp(he[color[a]],b,c);
    if(f[a][b][c]!=-1)return f[a][b][c];
    if(c==0){f[a][b][c]=0;return 0;}
    if(b==0){
        if(c>=w[a])f[a][b][c]=v[a];
        else f[a][b][c]=0;
        return f[a][b][c];
    }
    
    f[a][b][c]=dp(a,0,c);
    for(int j=0;j<=c-w[a];j++)
        f[a][b][c]=max(f[a][b][c],
        dp(a,b-1,c-j)+dp(g2[a][b-1],s2[g2[a][b-1]],j));
    return f[a][b][c];
}

int main(){
    memset(f,-1,sizeof(f));
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
        
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    
    int a;
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        if(a!=0){
            g[a].push_back(i);
            s[a]++; 
        }
        else ze[i]=1;
    }
    
    trans();//缩点
    
    printf("%d\n",dp(0,s2[0],m));
    
    return 0;
}