第一章动态规划（十一）
树形DP
例题：树的最长路径
也叫做树的直径
步骤：
- 任取一点，找到距离该点最远的一个点 u。—BFS
- 再找到距离 u 最远的一个点 v。—BFS
u 和 v 之间的路径就是一条直径。
我们将每个节点作为一个类，记录两条信息，一是以该节点为端点向下走的最长路径，也就是图中的 1，二是经过该端点的最长路径，也就是 1 + 2（1是最长距离，2是次长距离）。
import java.util.Arrays;
import java.util.Scanner;
class Main{
static int N = 10010;
static int M = N * 2;//边数=点*2
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] w = new int[N];
static int idx;
static int n;
static int ans;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
Arrays.fill(h, -1);
for(int i = 0;i < n - 1;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c);
add(b, a, c);
}
sc.close();
dfs(1, -1);//一开始没有父节点，置为-1
System.out.println(ans);
}
private static int dfs(int u, int father) {
int dist = 0;//表示从当前点往下走的最大长度
int d1 = 0, d2 = 0;//最长距离，次长距离
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == father) continue;
int d = dfs(j, u) + + w[i];
dist = Math.max(dist, d);
if (d >= d1) {
d2 = d1;
d1 = d;
}else if (d > d2) {
d2 = d;
}
}
ans = Math.max(ans, d1 + d2);
return dist;
}
private static void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
}
例题：1073. 树的中心
思路：求出每个点距离其他点的最远距离，取最小值即为答案。
import java.util.Arrays;
import java.util.Scanner;
class Main{
static int INF = Integer.MAX_VALUE >> 1;
static int N = 10010;
static int M = N * 2;//边数=点*2
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] w = new int[N];
static int idx;
static int[] d1 = new int[N];//往下走的最长距离
static int[] d2 = new int[N];//次长距离
static int[] up = new int[N];//往上走的最长距离
static int[] p1 = new int[N];
static int[] p2 = new int[N];
static int n;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
Arrays.fill(h, -1);
for(int i = 0;i < n - 1;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c);
add(b, a, c);
}
sc.close();
dfs_d(1, -1);//一开始没有父节点，置为-1
dfs_u(1, -1);
int ans = INF;
for (int i = 1; i <= n; i++) {
ans = Math.min(ans, Math.max(d1[i], up[i]));
}
System.out.println(ans);
}
private static int dfs_d(int u, int father) {//往下走的最长路径
d1[u] = -INF;
d2[u] = -INF;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == father) continue;
int d = dfs_d(j, u) + w[i];
if (d >= d1[u]) {
d2[u] = d1[u];
d1[u] = d;
p2[u] = p1[u];
p1[u] = j;
}else if (d > d2[u]) {
d2[u] = d;
p2[u] = j;
}
}
if (d1[u] == -INF) {
d1[u] = 0;
d2[u] = 0;
}
return d1[u];
}
private static void dfs_u(int u, int father) {//往上走的最长路径
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == father) continue;
if (p1[u] == j) {
up[j] = Math.max(up[u], d2[u]) + w[i];
}else {
up[j] = Math.max(up[u], d1[u]) + w[i];
}
dfs_u(j, u);
}
}
private static void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
}
例题：数字转换
【题目描述】
如果一个数 x的约数和 y （不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x。例如 4 可以变为 3，1 可以变为 7。限定所有数字变换在不超过 n的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。
【输入】
输入一个正整数 n。
【输出】
输出不断进行数字变换且不出现重复数字的最多变换步数。
【输入样例】
7
【输出样例】
3
【提示】
样例说明
一种方案为 4→3→1→7。
数据范围与提示：
对于 100% 的数据，1≤n≤50000。
————————————————————————————————————————————
对于每个 x，它的 y 是唯一的，所以我们将 y 看做 x 的父节点，本质是树的最长路径。
import java.util.Arrays;
import java.util.Scanner;
class Main{
static int N = 50010;
static int M = N * 2;//边数=点*2
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx;
static int n;
static int[] sum = new int[N];//约数之和
static boolean[] st = new boolean[N];//节点是否为根
static int ans;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
sc.close();
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= n / i; j++) {
sum[i * j] += i;
}
}
Arrays.fill(h, -1);
for (int i = 2; i <= n; i++) {//1的约数之和是0，不能枚举它
if (i > sum[i]) {
add(sum[i], i);
st[i] = true;
}
}
for (int i = 1; i <= n; i++) {
if (!st[i]) {
dfs(i);
}
}
System.out.println(ans);
}
private static int dfs(int u) {
int d1 = 0;
int d2 = 0;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
int d = dfs(j) + 1;//无权，权重就是1
if (d >= d1) {
d2 = d1;
d1 = d;
}else if (d > d2) {
d2 = d;
}
}
ans = Math.max(ans, d1 + d2);
return d1;
}
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}
例题：二叉苹果树
【题目描述】
有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共 N个节点，标号 1 至 N，树根编号一定为 1。
我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。
【输入】
第一行两个数 N和 Q ，N 表示树的节点数，Q表示要保留的树枝数量。
接下来 N−1行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。
【输出】
输出仅一行，表示最多能留住的苹果的数量。
【输入样例】
5 2
1 3 1
1 4 10
2 3 20
3 5 20
【输出样例】
21
【提示】
数据范围与提示：
对于 100% 的数据，1≤Q≤N≤100,N≠1，每根树枝上苹果不超过 30000 个。
—————————————————————————————————————————————————————
简化的有依赖的背包问题，想留下某个节点就必须留下它的父节点。
f[i][j]：以 i 为根的树中，选 j 条边的最大价值。
将每个子树看做一组物品
import java.util.Arrays;
import java.util.Scanner;
class Main{
static int N = 110;
static int M = N * 2;//边数=点*2
static int[] h = new int[N];
static int[] e = new int[M];
static int[] w = new int[M];
static int[] ne = new int[N];
static int idx;
static int n;
static int m;
static int[][] f = new int[N][N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(h, -1);
for (int i = 0;i < n - 1;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
add(a, b, c);
add(b, a, c);
}
sc.close();
dfs(1, -1);
System.out.println(f[1][m]);
}
private static void dfs(int u, int father) {
for (int i = h[u]; i != -1; i = ne[i]) {//枚举物品组
if (e[i] == father) continue;
dfs(e[i], u);
for (int j = m; j >= 0; j--) {//枚举体积 大-->小
for (int k = 0; k < j; k++) { //决策
f[u][j] = Math.max(f[u][j], f[u][j - k - 1] + f[e[i]][k] + w[i]);
}
}
}
}
private static void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
}
例题：323. 战略游戏
摘自–“小呆呆”
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main{
static int N = 1510;
static int M = N;
static int n;
static int m;
static int[][] f = new int[N][2];
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int idx = 0;
static boolean[] st = new boolean[N];
private static void add(int a,int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
private static void dfs(int u) {
f[u][1] = 1;f[u][0] = 0;
for(int i = h[u];i != -1;i = ne[i]) {
int j = e[i];
dfs(j);
f[u][0] += f[j][1];
f[u][1] += Math.min(f[j][1], f[j][0]);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) {
String str = br.readLine();
if (str == null) break;
int n = Integer.parseInt(str);
Arrays.fill(h, -1);
Arrays.fill(st, false);
idx = 0;
while(n -- > 0) {
String[] s = br.readLine().split(" ");
int a = Integer.parseInt(s[0].substring(0, s[0].indexOf(':')));
if(s.length > 1) {
for(int i = 1;i < s.length ;i ++) {
int b = Integer.parseInt(s[i]);
add(a,b);
st[b] = true;
}
}
}
int root = 0;
while(st[root]) root ++;
dfs(root);
System.out.println(Math.min(f[root][0], f[root][1]));
}
}
}
例题：皇宫看守
【题目描述】
太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。
皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状，某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。
可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
【输入】
输入中数据描述一棵树，描述如下：
第一行 n，表示树中结点的数目。
第二行至第 n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号 i(0<i≤n)，在该宫殿安置侍卫所需的经费 k，该边的儿子数 m，接下来 m 个数，分别是这个节点的 m 个儿子的标号r1,r2,⋯,rm。
对于一个 n个结点的树，结点标号在 1 到 n之间，且标号不重复。
【输出】
输出最少的经费
【输入样例】
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0
【输出样例】
25
【提示】
样例解释：
有六个区域被安排的情况如左图所示。
如右图，灰色点安排了警卫，2号警卫可以观察 1,2,5,6，3 号警卫可以观察 1,3，4 号警卫可以观察 1,4。
总费用：16+5+4=25
数据范围与提示：
对于 100% 的数据，0<n≤1500。
————————————————————————————————————————————————————
f[i][0] ： 点 i 被父节点看到的所有摆放方案中的最小花费。
f[i][1] ： 点 i 被子节点看到的所有摆放方案中的最小花费。
f[i][2]：在点 i 上放警卫的所有摆放方案的最小花费。
f[i][0] = 所有 min(f[j][1], f[j][2]) 的 和
f[i][2] = 所有 min(f[j][0], f[j][1], f[j][2]) 的 和
f[i][1] (需要枚举哪个子节点看到它) = 枚举k次 min{f[k][2] + 除k之外的所有 min(f[j][1], f[j][2]) 的和}
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int N = 1510;
static int n;
static int[][] f = new int[N][3];
static int[] h = new int[N];
static int[] e = new int[N];
static int[] w = new int[N];
static int[] ne = new int[N];
static int idx = 0;
static boolean[] st = new boolean[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
Arrays.fill(h, -1);
for (int i = 1; i <= n; i++) {
int id = sc.nextInt();
int cost = sc.nextInt();
int cnt = sc.nextInt();
w[id] = cost;
while(cnt-- > 0){
int ver = sc.nextInt();
add(id, ver);
st[ver] = true;
}
}
sc.close();
int root = 1;
while(st[root]) root++;
dfs(root);
System.out.println(Math.min(f[root][1], f[root][2]));
}
private static void dfs(int u) {
f[u][2] = w[u];//花费w[u]
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
dfs(j);
f[u][0] += Math.min(f[j][1], f[j][2]);
int tmp = Math.min(f[j][0], f[j][1]);
f[u][2] += Math.min(tmp, f[j][2]);
}
f[u][1] = Integer.MAX_VALUE >> 1;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
f[u][1] = Math.min(f[u][1], f[j][2] + f[u][0] - Math.min(f[j][1], f[j][2]));
}
}
private static void add(int a,int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
}
上一篇： 第一章动态规划（十四）
下一篇： P1101 单词方阵
推荐阅读
-
Mybaits 源码解析 （十一）----- 设计模式精妙使用：静态代理和动态代理结合使用：@MapperScan将Mapper接口生成代理注入到Spring
-
C++动态规划实现查找最长公共子序列
-
C#使用动态规划解决0-1背包问题实例分析
-
野生前端的数据结构练习（11）动态规划算法
-
C - Monkey and Banana HDU 1069( 动态规划+叠放长方体)
-
leadcode的Hot100系列--64. 最小路径和--权值最小的动态规划
-
2015微信电商购物双十一创意动态海报设计思路分享
-
动态规划算法题：机器人到达指定合位置方法数
-
南阳 ACM16 矩形嵌套 动态规划
-
leadcode的Hot100系列--62. 不同路径--简单的动态规划