清北学堂noip2019-DP图论-Day2树形DP

清北学堂noip2019-DP图论-Day2树形DP

简单入门题——没有上司的舞会

一棵树,每个点有权值,一个点和其儿子 / 父亲不能同时取,求解从树上选取点能获得的最大权值。 - 树形 DP 中的覆盖问题,同时是一个子树转移问题(当前树的最优解由子树的最优解得到) 对于这类问题,我们应该维护每个子树的最优解 并关注子树到根的转移方式

  • $dp[i][0]$ 表示我们不选择 $i$ 节点时子树的最大值 $dp[i][1]$ 表示我们选择 $i$ 节点时子树的最大值 转移方程,对于每个节点 $i$ 的所有子节点 $dp[i][0] += max(dp[j][0], dp[j][1])$ $dp[i][1] += dp[j][0]$
    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
    #include<bits/stdc++.h>
    using namespace std;
    int n,f[6009][2],value[6009],root;
    bool vis[6009];
    vector<int> son[6009];
    void dp(int u){
    f[u][0]=0;
    f[u][1]=value[u];
    for(int i=0;i<son[u].size();i++){
    int y=son[u][i];
    dp(y);
    f[u][0]+=max(f[y][0],f[y][1]);
    f[u][1]+=f[y][0];
    }
    }
    int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
    cin>>value[i];
    }
    while(1){
    int x,y;
    cin>>x>>y;
    if(x==y&&x==0) break;
    vis[x]=1;
    son[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
    if(vis[i]==0){
    root=i;
    break;
    }
    }
    dp(root);
    cout<<max(f[root][0],f[root][1]);
    return 0;
    }

Codeforce——767C Garland

给定一个树,树有点权 要求你把树的某些边删去,使得树变成三个部分 每个部分的点权值和都相等 题目 - 思路:可以想到,一旦能够找到一颗子树和为$w_总/3$就把它和它的父节点断开,即可。 - 原因:因为如果两颗子树的和各是总和的三分之一,那么它们一定不会有交集。


HDU 3586

给定一颗无向带权树,要切断所有叶子节点和根节点的联系,每次切断的费用不能超过上限 Limit,问在保证 总费用 <=m 的情况下最小的 Limit - 二分+树形DP - dp[u]表示u子树中上限为limit时符合条件的最小总费用。 那么可以这样设计转移:

1
2
3
4
5
6
if(dis(u,v)>limit){
dp[u]+=dp[v];
}
else{
dp[u]+=min(dp[u],dis(u,v));
}

Luogu P2458——保安站岗

设计状态$dp[i][0/1/2]$, - $dp[i][0]$表示靠父节点的控制 - $dp[i][1]$表示靠自己的控制 - $dp[i][2]$表示靠子节点的控制 这样即可推得状态转移方程: - $dp[u][0]=\sum min(dp[v][1],dp[v][2])$ - $dp[u][1]=\sum min(dp[v][0],dp[v][1],dp[v][2])+val[u]$ - $dp[u][2]=\sum min(dp[v][1],dp[v][2])+某一个dp[v][2]$(这个比较麻烦。。。)

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<bits/stdc++.h>
using namespace std;

vector<int> son[1509];
int n,v[1509],dp[1509][3];

void f(int x,int fa){
dp[x][0]=dp[x][1]=0;
for(int i=0;i<son[x].size();i++){
int y=son[x][i];
if(y==fa) continue;
f(y,x);
dp[x][0]+=min(dp[y][1],dp[y][2]);
dp[x][1]+=min(min(dp[y][0],dp[y][1]),dp[y][2]);
}
dp[x][1]+=v[x];dp[x][2]=0x3f3f3f3f;
for(int i=0;i<son[x].size();i++){
int y=son[x][i];
if(y==fa) continue;
dp[x][2]=min(dp[x][2],dp[x][0]-min(dp[y][1],dp[y][2])+dp[y][1]);
}
}

int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x,m;
cin>>x;
cin>>v[x];
cin>>m;
for(int i=1;i<=m;i++){
int y;
cin>>y;
son[x].push_back(y);
son[y].push_back(x);
}
}
f(1,-1);
cout<<min(dp[1][1],dp[1][2]);
return 0;
}

树上dp的链问题

有一类树上 DP 的问题,求的是树上的满足条件的“最优链” 经典问题:HDU 2196 给定一棵有边权的树,输出树中与其距离最远的点的距离值 - 显然,从一个节点x出发到达的点只有两种情况: 1. 在x的子树中。 2. 在x的子树外。

  • 显然第一种十分好维护,令 f[i] 表示以 i 为起点的,到 i 的子树内距离最远是多少 则 $f[i] = max(f[j] + dist(i,j))$ 那么第二种如何维护?我们令 $g[i]$ 表示 i 为起点到 i 的子树外距离最远是多少 第二种情况需要再做一次分类 一类是经过它的父亲,到父亲外,即 $g[i]$ <- $g[fa[i]]$ 另一类是经过它的父亲,到了它的兄弟子树中

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×