树形dp入门模板题-没有上司的舞会（动态规划）

54 阅读 0 评论 36 点赞

我是靠谱客的博主阔达雨，最近开发中收集的这篇文章主要介绍树形dp入门模板题-没有上司的舞会（动态规划），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

第一行一个整数N。(1<=N<=6000)

接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

最后一行输入0 0

输出格式

输出最大的快乐指数。

输入 #1

输出 #1

题目链接（洛谷）

树形dp
先来说一说个人对树形dp的理解，在思维上，其实它和我们常见的线性dp差不多，只是它递推的表现形式不是线性的，而是树形的推出来。在代码的写法上，常见的线性dp基本上用的是迭代的形式，也就是for循环，而树形dp是像树一样递推出来的，所有用的更多的是dfs和递归的写法。我们直接拿上面这道模板题来感受下树形dp。

题目中每一个职员都有两种情况，一种是参加，另一种是不参加。我们可以用一个二维数组来表示， dp[n+1][2] ,dp[i][0]表示该职员不参加时的最大快乐值，dp[i][1]表示该职员参加的最大快乐值。当该职员参加时，他的所有下属都不能参加即dp[y][0],将所有下属不参加的值加起来即可。当该职员不参加时，他的所有下属可以参加也可以不参加，取最大值加起来就可以了，即Max（dp[y][0],dp[y][1]）。光看文字是很枯燥的，建议拿笔在纸上画一画，很快理解了。

参考代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main 
{    
    public static void main(String args[]) 
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //存储每个职员参加的快乐指数
        int[] rs=new int[n+1];
        for(int i=1;i<=n;i++)
        	rs[i]=sc.nextInt();
        //记录每一个节点的所有子节点
        List<List<Integer>> ps=new ArrayList<List<Integer>>();
        for(int i=0;i<=n;i++)
        	ps.add(new ArrayList<Integer>());
        int[] book=new int[n+1];
        for(int i=1;i<n;i++)
        {
        	int x=sc.nextInt();
        	int y=sc.nextInt();
        	ps.get(y).add(x);
        	book[x]=1;
        }
        sc.nextInt();sc.nextInt();
        //找出该树的根节点
        int root=0;
        for(int i=1;i<=n;i++)
        	if(book[i]==0)
        	{
        		root=i;
        		break;
        	}
        int[][] dp=new int[n+1][2];
        //从根节点往下找
        dfs(ps,rs,dp,root);
        System.out.println(Math.max(dp[root][0], dp[root][1]));
        
    }

	private static void dfs(List<List<Integer>> ps,int[] rs, int[][] dp, int root) 
	{
		
		dp[root][1]=rs[root];
		for(int i=0;i<ps.get(root).size();i++)
		{
			int son=ps.get(root).get(i);
			dfs(ps, rs, dp, son);
			//当父节点选的时候,和只能等于所有子节点不选的和
			dp[root][1]+=dp[son][0];
			//当父节点不选的时候,所有的子节点都有选和不选两种情况,取最大值,将所有的子节点加起来
			dp[root][0]+=Math.max(dp[son][1], dp[son][0]);
		}
		
	}
}