devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2024-02-19（树形DP）

作者：知新_RL | 2024-02-22 01:46:28

赞

踩

2024-02-19（树形DP）

285. 没有上司的舞会 - AcWing题库树形dp的一道题2024-02-07（计数类DP、数位统计DP、状态压缩DP、树形 DP、记忆化搜索）-CSDN博客

1072. 树的最长路径 - AcWing题库 

找树的直径

1、任取一点作为起点，找到距离该点最远的点u  BFS, DFS

2、再找到距离u点最远的点v   BFS, DFS

        那么u和v之间的路径就是一条直径 

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     static int N = 10010, M = 2 * N;//因为是无向图，所以要开两倍的数组
  5.     static int[] h = new int[M], ne = new int[M], e = new int[M], w = new int[M];
  6.     static int n, res, idx;//res表示答案
  7.     
  8.     //邻接表存储无向图
  9.     public static void add(int a, int b, int c){
  10.         e[idx] = b;
  11.         w[idx] = c;
  12.         ne[idx] = h[a];
  13.         h[a] = idx ++;
  14.     }
  15.     
  16.     public static int dfs(int u, int father){
  17.         int dist = 0;//表示这个点往下走的最大长度
  18.         int d1 = 0;//这个点往下走的最大长度
  19.         int d2 = 0;//这个点往下走的第二大长度
  20.         for(int i = h[u]; i != -1; i = ne[i]){
  21.             int j = e[i];
  22.             if(j == father) continue;//由于只能往下走，如果等于父节点就说明往回走了，所以不行
  23.             
  24.             int d = dfs(j, u) + w[i];
  25.             dist = Math.max(dist, d);
  26.             if(d > d1){
  27.                 d2 = d1;
  28.                 d1 = d;
  29.             }else if(d > d2){
  30.                 d2 = d;
  31.             }
  32.         }
  33.         
  34.         res = Math.max(res, d1 + d2);
  35.         return dist;
  36.     }
  37.     
  38.     //开始main函数
  39.     public static void main(String[] args){
  40.         Scanner sc = new Scanner(System.in);
  41.         n = sc.nextInt();
  42.         
  43.         Arrays.fill(h, -1);
  44.         for(int i = 1; i < n; i ++){//一共有n-1条边
  45.             int a = sc.nextInt();
  46.             int b = sc.nextInt();
  47.             int c = sc.nextInt();
  48.             add(a, b, c);
  49.             add(b, a, c);
  50.         }
  51.         
  52.         dfs(1, -1);//取编号为1的点作为根节点，由于其没有父节点，所以让其父节点的参数为-1
  53.         
  54.         System.out.print(res);
  55.     }
  56. }

 

1073. 树的中心 - AcWing题库

暴力枚举：求出每个点到其他所有点的最远距离，然后取一个最小值 

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     static int N = 10010, M = 2 * N, idx, n, INF = 0x3f3f3f3f;
  5.     static int[] h = new int[M], ne = new int[M], e = new int[M], w = new int[M];//邻接表
  6.     static int[] d1 = new int[M];//往下走最长距离
  7.     static int[] d2 = new int[M];//往下走次长距离
  8.     static int[] p = new int[M];//记录最长路径是由哪个节点过来的
  9.     static int[] up = new int[M];//往上走的最长距离
  10.     
  11.     //邻接表存储
  12.     public static void add(int a, int b, int c){
  13.         e[idx] = b;
  14.         w[idx] = c;
  15.         ne[idx] = h[a];
  16.         h[a] = idx ++;
  17.     }
  18.     
  19.     //往下走找最长距离
  20.     public static int dfs_down(int u, int father){
  21.         d1[u] = 0;
  22.         d2[u] = 0;
  23.         
  24.         for(int i = h[u]; i != -1; i = ne[i]){
  25.             int j = e[i];
  26.             if(j == father) continue;
  27.             
  28.             int d = dfs_down(j, u) + w[i];
  29.             
  30.             if(d > d1[u]){
  31.                 d2[u] = d1[u];
  32.                 d1[u] = d;
  33.                 p[u] = j;
  34.             }else if(d > d2[u]){
  35.                 d2[u] = d;
  36.             }
  37.         }
  38.         
  39.         return d1[u];
  40.     }
  41.     
  42.     //往上走的最长距离
  43.     //有两个方向：父节点接着往上走，父节点往下走
  44.     public static void dfs_up(int u, int father){
  45.         for(int i = h[u]; i != -1; i = ne[i]){
  46.             int j = e[i];
  47.             if(j == father) continue;
  48.             
  49.             //如果父节点往下走的最长距离是经由这个节点来的，那么就用次长和往上走的距离比较，最后要加上这个点到父节点的距离
  50.             if(p[u] == j) up[j] = Math.max(d2[u], up[u]) + w[i];
  51.             else up[j] = Math.max(d1[u], up[u]) + w[i];
  52.             
  53.             dfs_up(j, u);
  54.         }
  55.     }
  56.     
  57.     //开始main函数
  58.     public static void main(String[] args){
  59.         Scanner sc = new Scanner(System.in);
  60.         n = sc.nextInt();
  61.         
  62.         Arrays.fill(h, -1);//初始化
  63.         
  64.         for(int i = 1; i < n; i ++){
  65.             int a = sc.nextInt();
  66.             int b = sc.nextInt();
  67.             int c = sc.nextInt();
  68.             add(a, b, c);
  69.             add(b, a, c);
  70.         }
  71.         
  72.         dfs_down(1, -1);//往下走
  73.         dfs_up(1, -1);//往上走
  74.         
  75.         int res = INF;
  76.         for(int i = 1; i <= n; i ++){
  77.             res = Math.min(res, Math.max(up[i], d1[i]));//找到每个点的两个方向的最大值，再从中取最小
  78.         }
  79.         
  80.         System.out.print(res);
  81.     }
  82. }

 

1075. 数字转换 - AcWing题库

每一个数的约数之和（不包括本身）都是固定的。将一个数（能转换）的约数之和作为它的父节点。那么问题就转化为 求树的最长路径问题。 

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     static int N = 50010;
  5.     static int[] h = new int[N], ne = new int[N], e = new int[N];
  6.     static int idx, n, res;
  7.     static boolean[] st = new boolean[N];
  8.     static int[] sum = new int[N];//约数之和
  9.     
  10.     //邻接表存储
  11.     public static void add(int a, int b){
  12.         e[idx] = b;
  13.         ne[idx] = h[a];
  14.         h[a] = idx ++;
  15.     }
  16.     
  17.     //dfs树的最长路径模板
  18.     public static int dfs(int u){
  19.         int d1 = 0;
  20.         int d2 = 0;
  21.         for(int i = h[u]; i != -1; i = ne[i]){
  22.             int j = e[i];
  23.             
  24.             int d = dfs(j) + 1;
  25.             if(d > d1){
  26.                 d2 = d1;
  27.                 d1 = d;
  28.             }else if(d > d2){
  29.                 d2 = d;
  30.             }
  31.         }
  32.         res = Math.max(res, d1 + d2);
  33.         return d1;
  34.     }
  35.     
  36.     public static void main(String[] args){
  37.         Scanner sc = new Scanner(System.in);
  38.         n = sc.nextInt();
  39.         
  40.         Arrays.fill(h, -1);//初始化
  41.         
  42.         //遍历1到n，判断这个数可以是哪些数的约数
  43.         for(int i = 1; i <= n; i ++){
  44.             for(int j = 2; j <= n / i; j ++){
  45.                 sum[i * j] += i;
  46.             }
  47.         }
  48.         
  49.         for(int i = 1; i <= n; i ++){
  50.             if(i > sum[i]){
  51.                 add(sum[i], i);//建立有向图，约数之和为其父节点
  52.                 st[i] = true;//有父节点
  53.             }
  54.         }
  55.         
  56.         for(int i = 1; i <= n; i ++){
  57.             if(!st[i]) dfs(i);//如果没有父节点的话，就遍历这一颗树
  58.         }
  59.         
  60.         dfs(1);
  61.         System.out.print(res);
  62.     }
  63. }

 

1074. 二叉苹果树 - AcWing题库

10. 有依赖的背包问题 - AcWing题库的简化版2024-02-12（背包模型）-CSDN博客

 

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     static int N = 110, M = 2 * N;
  5.     static int[] h = new int[M], ne = new int[M], e = new int[M];
  6.     static int idx, n, m;
  7.     static int[][] f = new int[M][M];//f[u][j]以u为根节点的树选j条边的最大价值
  8.     static int[] w = new int[M];//每一条边的价值
  9.     
  10.     //邻接表存储
  11.     public static void add(int a, int b, int c){
  12.         e[idx] = b;
  13.         w[idx] = c;
  14.         ne[idx] = h[a];
  15.         h[a] = idx ++;
  16.     }
  17.     
  18.     public static void dfs(int u, int father){
  19.         for(int i = h[u]; i != -1; i = ne[i]){//先枚举物品组
  20.             int son = e[i];
  21.             if(son == father) continue;//由于是无向图，所以要保证不往回走
  22.             
  23.             dfs(son, u);//递归！！！进行子节点的遍历
  24.             for(int j = m; j >= 0; j --){//再从大到小枚举体积
  25.                 for(int k = 0; k < j; k ++){//最后再枚举决策
  26.                     //这里j先减去1，是因为要留一条边给连接他的父节点
  27.                     f[u][j] = Math.max(f[u][j], f[u][j - 1 - k] + f[son][k] + w[i]);
  28.                 }
  29.             }
  30.         }
  31.     }
  32.     
  33.     public static void main(String[] args){
  34.         Scanner sc = new Scanner(System.in);
  35.         n = sc.nextInt();
  36.         m = sc.nextInt();
  37.         
  38.         Arrays.fill(h, -1);
  39.         for(int i = 1; i < n; i ++){
  40.             int a = sc.nextInt();
  41.             int b = sc.nextInt();
  42.             int c = sc.nextInt();
  43.             add(a, b, c);//建立无向图
  44.             add(b, a, c);
  45.         }
  46.         
  47.         dfs(1, -1);
  48.         System.out.print(f[1][m]);
  49.     }
  50. }

323. 战略游戏 - AcWing题库

和285. 没有上司的舞会 - AcWing题库 这道题很像2024-02-07（计数类DP、数位统计DP、状态压缩DP、树形 DP、记忆化搜索）-CSDN博客

没有上司的舞会：每条边上最多选一个点，求最大权值 。

战略游戏：每条边上至少选一个点，求最小权值。

1.  substring()方法-CSDN博客 

2.  indexOf()方法的使用，截取字符串，字符串截取，切割字符串，split()，join()，Replace()_val.indexof-CSDN博客

当题目说有多组测试数据，但又没有说明有多少组时，用while(sc.hasNext()) 

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     static int N = 1510;
  5.     static int[] h = new int[N], ne = new int[N], e = new int[N];
  6.     static int idx, n;
  7.     static int[][] f = new int[N][2];//f[u][0] f[u][1]
  8.     static boolean[] st = new boolean[N];//用来判断根节点
  9.     
  10.     //邻接表存储
  11.     public static void add(int a, int b){
  12.         e[idx] = b;
  13.         ne[idx] = h[a];
  14.         h[a] = idx ++;
  15.     }
  16.     
  17.     public static void dfs(int u){
  18.         //f[u][0] = 0;//初始化
  19.         f[u][1] = 1;
  20.         
  21.         for(int i = h[u]; i != -1; i = ne[i]){
  22.             int j = e[i];
  23.             
  24.             dfs(j);//递归
  25.             //dp思想分析
  26.             f[u][0] += f[j][1];
  27.             f[u][1] += Math.min(f[j][1], f[j][0]);
  28.         }
  29.     }
  30.     
  31.     public static void main(String[] args){
  32.         Scanner sc = new Scanner(System.in);
  33.         
  34.         while(sc.hasNext()){//多组测试数据
  35.             n = sc.nextInt();
  36.             
  37.             //由于有多组测试数据，所以每次都要进行初始化
  38.             idx = 0;
  39.             Arrays.fill(h, -1);
  40.             Arrays.fill(st, false);
  41.         
  42.             for(int i = 0; i < n; i ++){
  43.                 String str = sc.next();
  44.                 //输入
  45.                 int id = Integer.parseInt(str.substring(0, str.indexOf(":")));
  46.                 int cnt = Integer.parseInt(str.substring(str.indexOf('(') + 1, str.length() - 1));
  47.                 for(int j = 1; j <= cnt; j ++){
  48.                     int b = sc.nextInt();
  49.                     add(id, b);
  50.                     st[b] = true;
  51.                 }
  52.             }
  53.         
  54.             int root = 0;
  55.             while(st[root]) root ++;
  56.             dfs(root);
  57.         
  58.             System.out.println(Math.min(f[root][1], f[root][0]));//找到两个状态最小的那一个
  59.         }
  60.     }
  61. }

 

1077. 皇宫看守 - AcWing题库

战略游戏那道题看的是边，皇宫看守这道题看的是点。 

 

  1. import java.util.*;
  2.  
  3. public class Main{
  4.     static int N = 1510;
  5.     static int n, idx;
  6.     static int[] h = new int[N], ne = new int[N], e = new int[N];
  7.     static int[] w = new int[N];
  8.     static boolean[] st = new boolean[N];
  9.     static int[][] f = new int[N][3];
  10.     //f[u][0]表示点u没有放警卫，且点u被父节点看到的所有方案中的最小花费
  11.     //f[u][1]表示点u没有放警卫，且点u被子节点看到的所有方案中的最小花费
  12.     //f[u][2]表示在点u上放警卫的所有方案中的最小花费
  13.     
  14.     public static void add(int a, int b){
  15.         e[idx] = b;
  16.         ne[idx] = h[a];
  17.         h[a] = idx ++;
  18.     }
  19.     
  20.     public static void dfs(int u){
  21.         f[u][2] = w[u];//放警卫的花费
  22.         int sum = 0;
  23.         
  24.         for(int i = h[u]; i != -1; i = ne[i]){
  25.             int j = e[i];
  26.             
  27.             dfs(j);//递归
  28.             f[u][0] += Math.min(f[j][1], f[j][2]);//u被父节点看到，u的子节点的情况
  29.             sum += Math.min(f[j][1], f[j][2]);//用于f[u][0]的计算，其实这里的sum可以不用要，因为已经记录在f[u][0]里面了
  30.             f[u][2] += Math.min(Math.min(f[j][0], f[j][1]), f[j][2]);//u放警卫，u的儿子节点的情况
  31.         }
  32.         
  33.         f[u][1] = 0x3f3f3f3f;//要求最小值，先置为无穷大
  34.         for(int i = h[u]; i != -1; i = ne[i]){//自己放警卫的情况，要讨论它的所有子节点
  35.             int j = e[i];//当枚举到字节点j，子节点j放警卫，其他子节点放与不放都可以，找到最小花费的
  36.             f[u][1] = Math.min(f[u][1], f[j][2] + (sum - Math.min(f[j][1], f[j][2])));
  37.         }
  38.     }
  39.     
  40.     public static void main(String[] args){
  41.         Scanner sc = new Scanner(System.in);
  42.         n = sc.nextInt();
  43.         
  44.         Arrays.fill(h, -1);
  45.         for(int i = 1; i <= n; i ++){
  46.             int a = sc.nextInt();
  47.             w[a] = sc.nextInt();
  48.             int cnt = sc.nextInt();
  49.             while(cnt -- > 0){
  50.                 int b = sc.nextInt();
  51.                 add(a, b);
  52.                 st[b] = true;
  53.             }
  54.         }
  55.         
  56.         int root = 1;
  57.         while(st[root]) root ++;
  58.         
  59.         dfs(root);
  60.         
  61.         System.out.print(Math.min(f[root][1], f[root][2]));
  62.     }
  63. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/128025
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号