动态规划--树形DP

Posted on | In , | Visitors:

This is my blog.
（未完待续）
动态规划之树形dp。阅读此文前，需得知道什么是树，二叉树以及三种遍历方式。

重新打开树形DP，起因是不会做题——【2018.09.07】

一些问题

一些目前不会的问题，希望之后可以解决

  • 给定⼀棵n 个点的边权树，对于树中每个节点i，询问其到其它所有结点的距离和。 其中0 ≤ n ≤ 10^5

    如果i是根节点的话，即求节点i到所有子节点的距离之和

    dp[i]=∑(dp[j]+dist[i][j]*cnt[i]) f[j]=i

    但是如果是中间节点该怎么办咯？？？？？

好像有点想法了：

dp[i]=dp[f[i]]-(dp2[i]+cnt[i]*dist[f[i]][i])+(n-cnt[i])*dist[i][f[i]]+dp2[i]

就是【【父亲节点的所有子节的距离和-父亲节点到这颗子树的所有节点的之和 】+这两点的距离*这个点向上配对的点的个数】——向上的所有距离 + 向下的所有之和（这个易求，感觉可行呢！

​ 偶然发现了一道类似的题目，hdu 2196

​ 大概的意思就是，寻找最大的值

​ 一个节点的最大值就是，到子树节点的最大值和向上的最大值的最大值

​ 向下到子树节点的最大值易求；而向上的则是父亲节点不经过此节点的最大值加上这两点的距离之和

所以对于每一个节点，我们都需要维护三个值，一个是子代的最大值；第二个是第一个答案中经过的儿子节点的编号；第三个是不经过这个儿子节点的最大值；【看到很多博客说是次大值，害我理解了好久，不算次大值吧，可以在最后子代中分叉呀！应该说是在`dp[i]`点的时候的次大值吧
那么这个最大值的结果就可以如下表示了：

1
2
3
if(longest[f[i]]!=i) 
	ans[i]=max(longest[i],longest[f[i]]+dist[i][f[i]],dp[f[i]][1]+dist[i][f[i]]);
else ans[i]=max(longest[i],second[f[i]]+dist[i][f[i]],dp[f[i]][1]+dist[i][f[i]]);

简述

树形dp即在写转移方程时max或min中的参数不再只是两个了，而是多个。

dp建立在树上的，树【n个点，n-1条边】

目前看到的树形dp的类型有如下几种：

  • 根据树的特点，对于节点的父亲（爷爷、儿子）有要求的dp
  • 对于节点的子树有要求的dp
  • 对于节点到每个节点有要求的dp【目前没有想明白
  • 删除边，使得每一个联通块最多 最少满足几个子节点
  • 删除点，使得每一个联通块最多 最少满足几个子节点

思路

  • 多叉树变二叉树
  • 设dp[i][j]表示在以i为根的子树中，用大小为j的包能取得的最大价值

题集

没有上司的舞会

每个人不可以和上司参加舞会，但可以和上司的上司的……参加舞会

刚开始这样想，但这样的话是不对的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//以1为根节点
fa[1]=-1;
void dfs(int now){//每次将爷爷节点更新
    if(now==-1) return ;
    if(fa[now]==-1) return ;
    if(fa[fa[now]]==-1) return ;
    dp[fa[fa[now]])=max(dp[fa[fa[now]]],dp[now]+1);//
    dfs(fa[fa[now]]);
}
for(int i=1;i<=n;i++) dp[i]=val[i];
       
for(int i=2;i<=n;i++){//将叶子结点赋值
    if(in[i]==1){
        dfs(i);
    }
}

因为对于兄弟是可以一起参加的，这样感觉是不行的

难道把每一层都预处理（用dfs，搞出每一层的深度，然后相同深度的相加），然后一层一层搞

dp[i]=max(dp[i],dp[i-1]); i代表层数

这样我看最上面两层；其实这样也是不对的，因为对于i层，不一定所有的点都不可以取，比如他没有孩子的时候；然后我就放弃了这种想法

还有一种想法就是既然影响的人只是自己的父亲，和自己的孩子，那么我们可以这样假设

f[i]表示 i⼈参加了舞会的时候这个⼦树的欢乐值之和

g[i]表示 i ⼈没参加舞会的时候这个⼦树的欢乐值之和

f[i] = v[i] + ∑g[j] (fa[j]= i)

g[i] = max(f[j] , g[j] ) (fa[j] = i)

这时候的问题，就是这两个相互影响，初始值的问题

不过都是从孩子的影响开始的

所以对于树叶节点

f[i]=val[i] g[i]=0

也就是他是一层一层来进行更新的

加分二叉树

我们以加分二叉树为例

描述：

设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历

输入

第1行：一个整数n（n＜30），为节点个数。
第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。

输出

第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。
第2行：n个用空格隔开的整数，为该树的前序遍历。

分析

1.状态f[i][j]表示从i到j这颗子树的最高分
2.转移f[i][j]=Σmax(dfs(i,k-1)*dfs(k+1,j)+score[k](i<=k<=j));

AC代码

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
#include <iostream>
using namespace std;
int n;
long long score[35];
long long line[35][35];
int root[35][35];
long long dfs(int s,int e){
if(line[s][e])return line[s][e];
if(s>e){
line[s][e]=1;
return 1;
}
if(s==e){
line[s][e]=score[s];
root[s][e]=s;
return line[s][e];
}
long long ans=-1;
for(int i=s;i<=e;i++){
long long tmp;
tmp=dfs(s,i-1)*dfs(i+1,e)+score[i];
if(tmp>ans){
ans=tmp;
root[s][e]=i;
}
}
line[s][e]=ans;
return ans;
}
void outprint(int i,int j){
if(i>j)return ;
if(root[i][j]==n){
cout<<n<<endl;
return ;
}
cout<<root[i][j]<<" ";
outprint(i,root[i][j]-1);
outprint(root[i][j]+1,j);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>score[i];
cout<<dfs(1,n)<<endl;
outprint(1, n);
return 0;
}

转载请注明出处，谢谢。

愿 我是你的小太阳



买糖果去喽