每周一算法:树形动态规划

发布时间:2023年12月20日

树形动态规划

树形动态规划一般用于处理求树上最优值的问题。大多数动态规划问题都是在一维二维这种规则的背景下的,可以解决的问题比较局限,而树作为一种特殊的图,可以描述比较复杂的关系,再加上树的递归定义,是一种非常合适进行动态规划处理的数据结构。

具体来说,在树形动态规划当中,一般先算子树再进行合并。与树的后序遍历相似,都是先遍历子树,遍历完之后将子树的值传给父亲。简单来说就是先递归访问所有子树,再在根上合并。

了解了树形动态规划的基本思想后,下面来看一个树形动态规划的例题。

经典例题

题目链接

没有上司的舞会

题目描述

某大学有 n n n 个职员,编号为 1 … n 1\ldots n 1n

他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。

现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 h i h_i hi?,但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。

所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。

输入格式

输入的第一行是一个整数 n n n

2 2 2 到第 ( n + 1 ) (n + 1) (n+1) 行,每行一个整数,第 ( i + 1 ) (i+1) (i+1) 行的整数表示 i i i 号职员的快乐指数 h i h_i hi?

( n + 2 ) (n + 2) (n+2) 到第 2 n 2n 2n 行,每行输入一对整数 l , k l, k l,k,代表 k k k l l l 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

样例 #1

样例输入 #1

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

样例输出 #1

5

提示

数据规模与约定

对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 6 × 1 0 3 1\leq n \leq 6 \times 10^3 1n6×103 ? 128 ≤ h i ≤ 127 -128 \leq h_i\leq 127 ?128hi?127 1 ≤ l , k ≤ n 1 \leq l, k \leq n 1l,kn,且给出的关系一定是一棵树。

算法思想

从给出的测试样例,可以构建出这样一棵树。

在这里插入图片描述
从图中可以看出, 1 、 2 1、2 12的上司是 3 3 3 6 、 7 6、7 67的上司是 4 4 4,如果 3 、 4 3、4 34不参加舞会的话,邀请 1 、 2 、 5 、 6 、 7 1、2、5、6、7 12567,可以使快乐指数最大为 5 5 5。由此可见:

  • 对树中每个结点有 2 2 2种选择,邀请或者不邀请
  • 结点的选择与否会影响其子结点:某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会

因此,在状态表示时需要考虑树的整体收益,以及结点的状态(邀请或者不邀请)。

状态表示

  • f [ i ] [ 0 ] f[i][0] f[i][0]表示以 i i i为根的子树,在不邀请根结点 i i i时的最大快乐指数
  • f [ i ] [ 1 ] f[i][1] f[i][1]表示以 i i i为根的子树,在邀请根结点 i i i时的最大快乐指数

不妨设整棵树的根结点为 r r r,那么最终答案是 f [ r ] [ 0 ] f[r][0] f[r][0] f [ r ] [ 1 ] f[r][1] f[r][1]的最大值。

状态计算

对于 i i i为根的子树,考虑当前的根结点 i i i的状态:

  • 如果不邀请 i i i,那么可以选择邀请或者不邀请其子结点 j j j,因此可以递归计算出 f [ j ] [ 0 ] f[j][0] f[j][0] f [ j ] [ 1 ] f[j][1] f[j][1],取二者的最大值进行累加,即 f [ i ] [ 0 ] = ∑ m a x ( f [ j ] [ 0 ] , f [ j ] [ 1 ] ) f[i][0]=\sum max(f[j][0],f[j][1]) f[i][0]=max(f[j][0],f[j][1]),其中 j j j i i i的所有子结点。
  • 如果邀请 i i i,那么不能邀请其子结点 j j j,因此可以递归计算出 f [ j ] [ 0 ] f[j][0] f[j][0] f [ i ] [ 0 ] = ∑ ( f [ j ] [ 0 ] ) f[i][0]=\sum (f[j][0]) f[i][0]=(f[j][0]),其中 j j j i i i的所有子结点。

初始状态

f [ i ] [ 1 ] f[i][1] f[i][1]表示在邀请根结点 i i i时的最大快乐指数,其初始值为 h [ i ] h[i] h[i]

时间复杂度

由于在递归的过程每个点都只会算一次,所以总的时间复杂度为 O ( n ) O(n) O(n)

代码实现

#include <iostream>
#include <vector>
using namespace std;

const int N = 6010;
int h[N]; //快乐指数
int fa[N]; //保存每个结点的父节点
//邻接表存储树
vector<int> g[N];
//f[i][0]表示以i为根的子树,在不邀请根结点i时的最大快乐指数
//f[i][1]表示以i为根的子树,在邀请根结点i时的最大快乐指数
int f[N][2];
void dfs(int i)
{
    f[i][1] = h[i]; //初始状态
    for(int j : g[i]) //遍历i的子结点
    {
        dfs(j); //递归计算以j为根的子树
        f[i][0] += max(f[j][0], f[j][1]);
        f[i][1] += f[j][0];
    }
}
int main()
{
    int n;
    cin >> n;
    //输入快乐指数
    for(int i = 1; i <= n; i ++) cin >> h[i];
    //构建树
    for(int i = 1; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        g[b].push_back(a); //a是b的子结点
        fa[a] = b; //a的父节点是b
    }
    //确定根结点
    int r = 1;
    while(fa[r]) r = fa[r];
    dfs(r);
    cout << max(f[r][0], f[r][1]);
    return 0;
}
文章来源:https://blog.csdn.net/qiaoxinwei/article/details/134987567
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。