动态规划
搜索
- Flood Fill思想

A动态规划
三角形			方格取数*
上升子序列	怪盗基德的滑翔翼	登山	合唱队形	友好城市
	拦截导弹	导弹防御系统			*
	最长公共上升子序列				*
背包	菜药	装箱问题	宠物小精灵之收服*		基础
	数字组合	买书	货币系统	简化货币系统	组合方案
	庆功会	多重背包问题 III			多重背包
状态机
状压
区间
树形
数位
单调队列优化
斜率优化

B搜索
Flood Fill	池塘计数	城堡问题	山峰和山谷

基础代码

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
    }
}

动态规划

数字三角形模型

摘花生

最低通行费

方格取数

import java.util.*;
class Main{
    /*
      基本思路：dp[x1][y1][x2][y2]表示同时走到两个坐标的最大值
      由于是同时在走，存在关系：x1+y1 = x2+y2 = d,其中d是横纵坐标的相加的和
      因此状态可以表示为 dp[x1][x2][d]
      属性：最大值
      涉及的之前的状态划分：
      dp[x1-1][x2-1][d-1],dp[x1-1][x2][d-1],dp[x1][x2-1][d-1],dp[x1][x2][d-1]  
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] mat = new int[N+1][N+1];
        while(true){
            int r = sc.nextInt(),c = sc.nextInt(),v = sc.nextInt();
            if(r == 0 && c == 0 && v == 0) break;
            mat[r][c] = v;
        }
        int[][][] dp = new int[N*2+1][N+1][N+1];
        for(int d = 2;d <= 2*N;++d){
            for(int r1 = 1;r1 <= N;++r1){
                for(int r2 = 1; r2 <= N;++r2){
                    int c1 = d-r1,c2 = d-r2;
                    if(c1 < 1 || c1 > N || c2 < 1 || c2 > N) continue;  // 注意范围!!!!!!!!
                    if(r1 == r2){                                       // 同时走的两条路径出现交点，但是只能取一次数
                        dp[d][r1][r2] = mat[r1][c1];
                    }else{
                        dp[d][r1][r2] = mat[r1][c1]+mat[r2][c2];       // 同时走的两条路径没有交点，取到2个数字
                    }
                    int tmp1 = Math.max(dp[d-1][r1-1][r2],dp[d-1][r1][r2-1]);
                    int tmp2 = Math.max(dp[d-1][r1-1][r2-1],dp[d-1][r1][r2]);
                    dp[d][r1][r2] += Math.max(tmp1,tmp2);               //  从可能的四个前置状态中选出最大值
                }
            }
        }
        System.out.println(dp[2*N][N][N]);
    }
}

传纸条

最长上升子序列模型

基本的算法：1）动态规划求解（n^2） 2）二分求解(n*logn)
难点：分析题意联想到该模型

怪盗基德的滑翔翼

import java.util.*;
class Main{
    /*
       基本思路：求正向的最长下降（严格）子序列和反向的最长下降（严格）子序列
       评论区问题： 反向的最长下降子序列 是否等价于 正向的最长上升子序列 ?
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int[] arr = new int[101];
        int[] high = new int[101],low = new int[101];
        while(k-- > 0){
            int n = sc.nextInt();
            for(int i = 0;i < n;++i) arr[i] = sc.nextInt();
            high[0] = 1; low[0] = 1;
            int res = 0;
            for(int i = 1;i < n;++i){
                high[i] = 1; low[i] = 1;
                for(int j = 0;j < i;++j){
                    if(arr[i] > arr[j]) high[i] = Math.max(high[j]+1,high[i]);
                    if(arr[i] < arr[j]) low[i] = Math.max(low[j]+1,low[i]);
                }
                res = Math.max(res,Math.max(high[i],low[i]));
            }
            System.out.println(res);
        }
    }
}

登山

import java.util.*;
class Main{
    /*
       分析非常关键：
       1）按照顺序来浏览这些景点   => 获取一个子序列
       2）不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了 => 子序列必定是先严格单调递增后严格单调下降（山峰状）
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] low = new int[N],arr = new int[N],high = new int[N];
        for(int i = 0;i < N;++i) arr[i] = sc.nextInt();
        // high[i]表示以arr[i]结尾的最长上升子序列长度
        Arrays.fill(high,1);
        for(int i = 1;i < N;++i){
            for(int j = 0;j < i;++j){
                if(arr[i] > arr[j]){
                    high[i] = Math.max(high[i],high[j]+1);
                }
            }
        }
        // low[i]表示以arr[i]开头的最长下降子序列长度
        Arrays.fill(low,1);
        for(int i = N-2;i >= 0;--i){
            for(int j = i+1;j < N;++j){
                if(arr[i] > arr[j]){
                    low[i] = Math.max(low[i],low[j]+1);
                }
            }
        }
        int res = 0;
        for(int i = 0;i < N;++i){
            res = Math.max(res,low[i] + high[i] -1);
        }
        System.out.println(res);
    }
}

合唱队形

import java.util.*;
class Main{
    /*
        题意：求最长的子序列，满足先严格单调增后严格单调减
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] low = new int[N],arr = new int[N],high = new int[N];
        for(int i = 0;i < N;++i) arr[i] = sc.nextInt();
        // high[i]表示以arr[i]结尾的最长上升子序列长度
        Arrays.fill(high,1);
        for(int i = 1;i < N;++i){
            for(int j = 0;j < i;++j){
                if(arr[i] > arr[j]){
                    high[i] = Math.max(high[i],high[j]+1);
                }
            }
        }
        // low[i]表示以arr[i]开头的最长下降子序列长度
        Arrays.fill(low,1);
        for(int i = N-2;i >= 0;--i){
            for(int j = i+1;j < N;++j){
                if(arr[i] > arr[j]){
                    low[i] = Math.max(low[i],low[j]+1);
                }
            }
        }
        int res = 0;
        for(int i = 0;i < N;++i){
            res = Math.max(res,low[i] + high[i] -1);
        }
        System.out.println(N-res);
    }
}

友好城市

import java.util.*;
class Main{
    /*
        要求：选出最长的严格单调的子序列，子序列中每个元素是二元组(a,b)
        显然：只要保证元组的单调性，一定不会出现相加的情况
        方法：可以转换为LIS模型
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] point = new int[N][2];
        for(int i = 0;i < N;++i){
            point[i][0] = sc.nextInt(); point[i][1] = sc.nextInt();
        }
        Arrays.sort(point,(o1,o2)->{                  // 保证一维有序
            return Integer.compare(o1[0],o2[0]);
        });
        int[] dp = new int[N];
        int res = 0;
        Arrays.fill(dp,1);
        for(int i = 1;i < N;++i){
            for(int j = 0;j < i;++j){
                if(point[i][1] > point[j][1]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            res = Math.max(res,dp[i]);
        }
        System.out.println(res);
    }
}

最大上升子序列和

import java.util.*;
class Main{
    /*
        要求：求所有上升子序列的和的最大值，由于题目数据范围都是正整数
        dp[i]:表示以arr[i]结尾的最大上升子序列和
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N],dp = new int[N];
        for(int i = 0;i < N;++i){
            arr[i] = sc.nextInt(); dp[i] = arr[i];
        }
        int res = arr[0];
        for(int i = 1;i < N;++i){
            for(int j = 0;j < i;++j){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[j]+arr[i],dp[i]);
                }
            }
            res = Math.max(res,dp[i]);
        }
        System.out.println(res);
    }
}

拦截导弹

import java.util.*;
class Main{
    /*
        问题1：求最长不上升子序列？
        问题2：最少需要多少个不上升子序列可以覆盖整个序列
        解决思路：
           贪心思想：从前往后扫描每个数，对于每个数
           情况1：现有所有子序列结尾小于当前数，则创建新子序列
           情况2：将当前数放到所有大于等于当前数的子序列结尾中最小的那个子序列后面
        最终答案就是子序列个数
        注意：问题1和2都可以优化为 n*log(n)算法
        问题2的解决流程与求最长上升子序列的贪心解法是一致的。
        背后蕴含着离散数学的原理:狄尔沃斯定理(Dilworth's theorem)亦称偏序集分解定理，
        贪心思路证明：
        证明A = B 等价于 证明 A >= B 且 A <= B 其中A表示贪心算法得到的序列个数，B表示最优解
        显然B >= A成立
        证明：A <= B 
        采用调整法证明，假设存在不同于贪心法得到的序列的最优解，可以通过调整序列得到贪心法序列，即最优解经过调整后不会增加长度
        可以得到贪心解
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[(int)(1e3+10)];
        int n = 0;
        while(sc.hasNext()){
            arr[n++] = sc.nextInt();
        }
        int[] dp = new int[n],up = new int[n];
        /*求最长不上升子序列*/
        Arrays.fill(dp,1);
        int res1 = 1;
        for(int i = 1;i < n;++i){
            for(int j = 0;j < i;++j){
                if(arr[i] <= arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            res1 = Math.max(res1,dp[i]);
        }
        /*求最少覆盖的序列个数*/
        // up是严格递增的，找到第一个大于等于当前元素的末尾等价于找到大于等于当前元素的最小末尾序列元素
        int idx = 0;
        for(int i = 0;i < n;++i){
            int k = 0;
            while(k < idx && up[k] < arr[i]) ++k;      
            up[k] = arr[i];
        }
        System.out.printf("%d\n",res1);
        System.out.printf("%d\n",idx);
    }
}

导弹防御系统

import java.util.*;
class Main{
    /*
        问题:最少需要多少个上升/下降子序列覆盖原始序列？
        基本思路：贪心策略(参考拦截导弹的贪心思路)+dfs枚举
        方法：DFS求最小步数: 1)迭代加深 2)更新全局最小值
        bfs相比较dfs的缺点： 1）搜索需要大量空间(dfs只存路径) 2）不方便剪枝
    */
    public static int N = 51;
    public static int[] arr = new int[N];
    public static int[] up = new int[N],down = new int[N];
    public static int n,res;
    /*当前数，上升子序列个数，下降子序列个数*/
    public static void dfs(int idx,int upNum,int downNum){
        /*剪枝,不然超时*/
        if(upNum + downNum >= res) return;
        if(idx == n){
            res = Math.min(res,downNum + upNum);
            return;
        }
        /*情况1：贪心法构造上升子序列*/
        int k = 0;
        while(k < upNum && up[k] >= arr[idx]) ++k;
        int t = up[k];
        up[k] = arr[idx];
        if(k == upNum) dfs(idx+1,upNum+1,downNum);
        else dfs(idx+1,upNum,downNum);
        up[k] = t;
        /*情况2：贪心法构造下降子序列*/
        k = 0;
        while(k < downNum && down[k] <= arr[idx]) ++k;
        t = down[k];
        down[k] = arr[idx];
        if(k == downNum) dfs(idx+1,upNum,downNum+1);
        else dfs(idx+1,upNum,downNum);
        down[k] = t;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            n = sc.nextInt(); res = Integer.MAX_VALUE;
            if(n == 0) break;
            for(int i = 0;i < n;++i) arr[i] = sc.nextInt();
            dfs(0,0,0);
            System.out.println(res);
        }
    }
}

最长公共上升子序列

import java.util.*;
class Main{
    /*
        最长公共上升子序列解题思路：
        dp[i][j]:a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合（通过结尾元素划分集合）
        状态转移:
        1)不包含有a[i], dp[i-1][j] 
        2)包含a[i], 当a[i] == b[j], 则 max(dp[i-1][1~(j-1)]+1) 当a[i] > b[j] (严格递增)
        dp[i][j]为上面两种情况较大值
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N+1],b = new int[N+1];
        for(int i = 1;i <= N;++i) a[i] = sc.nextInt();
        for(int i = 1;i <= N;++i) b[i] = sc.nextInt();
        int res = 0;
        int[][] dp = new int[N+1][N+1];
        for(int i = 1;i <= N;++i){
            int maxv = 1;
            for(int j = 1;j <= N;++j){
                dp[i][j] = dp[i-1][j];                                    // 情况1：不包含a[i]
                if(a[i] == b[j]) dp[i][j] = Math.max(dp[i][j],maxv);      // 情况2：包含a[i]
                if(a[i] > b[j]) maxv = Math.max(maxv,dp[i-1][j]+1);       //维护dp[i-1][(1-j-1)]的最大值（注意该行与上一行顺序不能颠倒）
                res = Math.max(res,dp[i][j]);
            }
        }
        System.out.println(res);
    }
}

3780 构造数组(思维训练)

import java.util.*;
class Main{
    /*
      基本思想：
      题目可以转换为满足要求的和最大的单峰函数。
      考虑:枚举数组的每个位置作为峰值，求出当前位置作为峰值的单峰函数最大值。
      令位置k作为峰值，则需要求[0,k]的最大和leftSum与[k,n-1]的最大和rightSum
      最终和等于：leftSum[k]+rightSum[k]-nums[k]
      优化点：如何快速确定每个位置k作为峰值，其单峰函数最大值。
      单调栈优化:leftSum[k] = (k-j)*nums[k]+leftSum[j]     其中j为第一个小于nums[k]的数字的下标。
      通过上面的状态转移我们可以利用其他位置的计算结果。
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] nums = new long[n];
        for(int  i = 0;i < n;++i){
            nums[i] = sc.nextLong();
        }
        Stack<Integer> st = new Stack();
        int[] leftIndex = new int[n];
        Arrays.fill(leftIndex,-1);
        // 左边第一个小于该元素的坐标
        for(int i = n-1;i >= 0;--i){
            while(!st.isEmpty() && nums[st.peek()] > nums[i]){ // 递增栈
                int idx = st.pop();
                leftIndex[idx] = i;
            }
            st.push(i);
        }
        // 右边第一个小于该元素坐标
        st.clear();
        int[] rightIndex = new int[n];
        Arrays.fill(rightIndex,n);
        for(int i = 0;i < n;++i){
            while(!st.isEmpty() && nums[st.peek()] > nums[i]){
                int idx = st.pop(); rightIndex[idx] = i;
            } // 递增栈
            st.push(i);
        }
        /*当前位置k作为峰值，区间[0,k]的和*/
        long[] leftSum = new long[n];
        for(int i = 0;i < n;++i){
            int idx = leftIndex[i];
            leftSum[i] = (i-idx)*nums[i];
            long tmp = idx == -1 ? 0 : leftSum[idx];
            leftSum[i] += tmp;
        }
         /*当前位置k作为峰值，区间[k,n-1]的和*/
        long[] rightSum = new long[n];
        for(int i = n-1;i >= 0;--i){
            int idx = rightIndex[i];
            rightSum[i] = (idx-i)*nums[i];
            long tmp = idx == n ? 0 : rightSum[idx];
            rightSum[i] += tmp;
        }
        long res = Long.MIN_VALUE;
        int maxIndex = -1;
        for(int i = 0;i < n;++i){
            long cur = leftSum[i]+rightSum[i]-nums[i];   // 区间和[0,i]+区间和[i,n-1]-nums[i]
            if(cur > res){
                res = cur;
                maxIndex = i;
            }
        }
        for(int i = maxIndex-1;i >= 0;--i){
            nums[i] = Math.min(nums[i],nums[i+1]);
        }
        for(int i = maxIndex+1;i < n;++i){
            nums[i] = Math.min(nums[i],nums[i-1]);
        }
        for(int i = 0;i < n;++i){
            System.out.printf("%d ",nums[i]);
        }
    }
}

背包模型

菜药

import java.util.*;
class Main{
    /*
       基本思路：0-1背包问题
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(),M = sc.nextInt();
        int[][] arr = new int[M][2];
        for(int i = 0;i < M;++i){
            arr[i][0] = sc.nextInt(); arr[i][1] = sc.nextInt();
        }
        int[] dp = new int[T+1];
        for(int i = 0;i < M;++i){
            for(int j = T;j >= arr[i][0];--j){
                dp[j] = Math.max(dp[j],arr[i][1] + dp[j-arr[i][0]]);
            }
        }
        System.out.println(dp[T]);
    }
}

装箱问题

import java.util.*;
class Main{
    /*
       基本思路：0-1背包问题
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt(),n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i < n;++i) arr[i] = sc.nextInt();
        int[] dp = new int[V+1];
        for(int i = 0;i < n;++i){
            for(int j = V;j >= arr[i];--j){
                dp[j] = Math.max(dp[j],arr[i] + dp[j-arr[i]]);
            }
        }
        System.out.println(V - dp[V]);
    }
}

宠物小精灵之收服*

import java.util.*;
class Main{
    /*
       基本思路：0-1背包问题 + 回溯获取真实值
       实际上也可以另外开一个二维数组同步记录伤害值，比较费空间
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(),M = sc.nextInt(),K = sc.nextInt();
        int[] nums = new int[K],damage = new int[K];
        for(int i = 0;i < K;++i){
            nums[i] = sc.nextInt(); damage[i] = sc.nextInt();
        }
        int[][] dp = new int[N+1][M];
        for(int i = 0;i < K;++i){
            for(int j = N;j >= nums[i];--j){
                for(int k = M-1;k >= damage[i];--k)// 这里注意体力不能为0
                    dp[j][k] = Math.max(dp[j][k],1 + dp[j-nums[i]][k-damage[i]]);
            }
        }
        /*通过回溯获取收服最多小精灵都同时的最小伤害*/
        int t = M-1;
        while(t > 0 && dp[N][t] == dp[N][t-1]) --t;
        System.out.printf("%d %d\n",dp[N][M-1],M-t);
    }
}

数字组合

import java.util.*;
class Main{
    /*
       基本思路：和为M的方案数目转换为0-1背包
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(),M = sc.nextInt();
        int[] dp = new int[M+1];
        dp[0] = 1;
        for(int i = 0;i < N;++i){
            int v = sc.nextInt();
            for(int j = M;j >= v;--j){
                dp[j] = dp[j] + dp[j-v];
            }
        }
        System.out.println(dp[M]);
    }
}

买书

import java.util.*;
class Main{
    /*
       dp[i][j]: 前i个物品，价格恰好为j的方案数目
       按照选取的第i个物品的个进行集合划分：
       1）不选i dp[i-1][j]
       2）选1个i,dp[i-1][j-w_i]
       ...
       3 选n个i,dp[i-1][j- n*w_i]
       1) dp[i][j] = dp[i-1][j] + dp[i-1][j-w] + dp[i-1][j-2w] + ... + dp[i-1][j-nw], j-nw >= 0
       2) dp[i][j-w] = dp[i-1][j-w] + dp[i-1][j-2w] + ... + dp[i-1][j-n*w], j-nw >= 0
       联立1),2)得：
       dp[i][j] = dp[i-1][j] + dp[i][j-w]
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;
        int[] w = {10,20,50,100};
        for(int i = 0;i < 4;++i){
            for(int j = w[i];j <= n;++j){
                dp[j] = dp[j] + dp[j-w[i]];
            }
        }
        System.out.println(dp[n]);
    }
}

货币系统

import java.util.*;
class Main{
    /*
      同上
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(),m = sc.nextInt();
        long[] dp = new long[m+1];
        dp[0] = 1;
        for(int i = 0;i < n;++i){
            int w = sc.nextInt();
            for(int j = w;j <= m;++j){
                dp[j] = dp[j] + dp[j-w];
            }
        }
        System.out.println(dp[m]);
    }
}

简化货币系统

import java.util.*;
class Main{
    /*
       思路：最优解是原有货币系统的子集
       如何判断该元素是否多余？
       当元素ai能够被小于它的元素集合线性表示出时，那么该元素就是在货币系统中是多余的,。
       解题思路：排序+完全背包进行判断
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int n = sc.nextInt();
            int[] arr = new int[n];
            for(int i = 0;i < n;++i) arr[i] = sc.nextInt();
            Arrays.sort(arr);
            int mv = arr[n-1];
            int ans = 0;
            boolean[] dp = new boolean[mv+1];    // dp[i]表示面额i能够被之前的元素给凑出
            dp[0] = true;
            for(int i = 1;i <= n;++i){
                if(dp[arr[i-1]]) continue;       // 已经被之前组合出则该面值是多余的
                ++ans;                           // 不能被面额小的元素组合出，必须有一张该面额的元素
                for(int j = arr[i-1];j <= mv;++j){
                    dp[j] = dp[j] | dp[j-arr[i-1]];
                }
            }
            System.out.println(ans);
        }
    }
}

多重背包

多重背包问题	基本思路	时间复杂度
朴素解决	转化为0-1背包	物品总的数目 * 背包容量
二进制拆分优化	对每种物品进行二进制拆分，降低物品总数	降低后的物品总数*背包容量
单调队列优化	状态计算时对背包容量进行分类，采用单调队列优化	物品的种类数目 * 背包容量

多重背包特点：与0-1背包和完全背包不同，物品的个数是有限个的
问题解决思路：
   转换为0-1背包问题，总的时间复杂度：物品总数 * 背包容量
优化思路：对物品进行二进制拆分，降低每种物品的物品数目

庆功会

import java.util.*;
class Main{
    /*
       多重背包朴素解法:采用0-1背包的方式枚举所有物品
       优化策略1:二进制优化转换为0-1背包
       优化策略2：单调队列优化
       朴素的时间复杂度：物品的总的数目 * 背包容量
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(),V = sc.nextInt();
        int[] nums = new int[N+1],v = new int[N+1],w = new int[N+1];
        for(int i = 1;i <= N;++i){
            v[i] = sc.nextInt(); w[i] = sc.nextInt(); nums[i] = sc.nextInt(); 
        }
        int[] dp = new int[V+1];
        for(int i = 1;i <= N;++i){
            for(int j = 0;j < nums[i];++j){
                for(int k = V; k >= v[i];--k){
                    dp[k] = Math.max(dp[k],dp[k-v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[V]);
    }
}

多重背包问题 III

import java.util.*;
class Main{
    /*
       多重背包的单调队列优化
       dp[i][j]:表示考虑前i个物品，背包容量为j的最大价值。
       单调队列作用：用于快速获取上一层状态集合的最大值
       优化思路：见官方题解
       时间复杂度： 物品种类*背包容量
       空间优化：可以采用滚动数组优化
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(),V = sc.nextInt();
        int[] nums = new int[N+1],v = new int[N+1],w = new int[N+1];
        for(int i = 1;i <= N;++i){
            v[i] = sc.nextInt(); w[i] = sc.nextInt(); nums[i] = sc.nextInt(); 
        }
        int[][] dp = new int[N+1][V+1];
        int[] q = new int[20100];                // 单调递减队列中维护的是体积
        for(int i = 1;i <= N;++i){
            for(int r = 0;r < v[i];++r){         // 对容量进行分类（两层循环本质上对容量进行枚举）
                int head = 0,tail = -1;          // 清空单调队列
                for(int j = r;j <= V;j += v[i]){
                    while(head <= tail && j-q[head] > nums[i] * v[i]) ++head;                                 // 维护窗口大小,(j-q[tail])/v[i]*w[i]表示选择当前的物品个数*价值
                    while(head <= tail && dp[i-1][q[tail]] + (j-q[tail])/v[i]*w[i] <= dp[i-1][j]) --tail;  // 维护窗口最大值
                    q[++tail] = j;
                    dp[i][j] = dp[i-1][q[head]] + (j-q[head])/v[i]*w[i];
                }
            }
        }
        System.out.println(dp[N][V]);
    }
}

二维费用的背包问题

import java.util.*;
class Main{
    /*
        0-1背包思路，状态表示时多了一个维度
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), V = sc.nextInt(),M = sc.nextInt();
        int[][] dp = new int[V+1][M+1];
        for(int i = 1;i <= N;++i){
            int v = sc.nextInt(),m = sc.nextInt(),w = sc.nextInt();
            for(int j = V;j >= v;--j){
                for(int k = M;k >= m;--k){
                    dp[j][k] = Math.max(dp[j][k],dp[j-v][k-m]+w);
                }
            }
        }
        System.out.println(dp[V][M]);
    }
}

1020. 潜水员

import java.util.*;
class Main{
    /*
      基本思路：多维0-1背包问题
      注意本题对于两个维度“体积”的限制：体积至少是
      思维拓展："体积"不超过或者"体积恰好"的初始化和状态转移
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(),n = sc.nextInt();
        int k = sc.nextInt();
        // dp[j][k]表示氧气至少为j,氮气至少为k的最小重量
        int[][] dp = new int[m+1][n+1];
        for(int i = 0;i <= m;++i) Arrays.fill(dp[i],Integer.MAX_VALUE);  // 表示不可达状态
        dp[0][0] = 0;
        for(int i = 1;i <= k;++i){
            int a = sc.nextInt(),b = sc.nextInt(),c = sc.nextInt();
            for(int j = m;j >= 0;--j){
                for(int t = n;t >= 0;--t){
                    int jj = Math.max(0,j-a),tt = Math.max(0,t-b);        // 注意这里的负数也是合法状态等价于0
                    if(dp[jj][tt] != Integer.MAX_VALUE)
                        dp[j][t] = Math.min(dp[j][t],dp[jj][tt] + c);
                }
            }
        }
        System.out.println(dp[m][n]);
    }
}

状态机模型

预备知识

更多关于状态机参考文章有限状态机的理解

有限状态机定义（FSM）：有一系列的状态（state）。根据输入的不同，FSM 从一个状态切换到另一个状态。在这些状态中，有一些状态是特殊的状态 —— 接受状态（accept state）。如果输入处理完毕，FSM 停留在接受状态，那么 FSM 处理成功，否则处理失败，

实例1：

写一个状态机，验证一串二进制bit，包含偶数个0和奇数个1。

状态定义

	状态1	状态2	状态3	状态4
定义	偶数个 0 和偶数个 1	偶数个 0 和奇数个 1	奇数个 0 和偶数个 1	奇数个 0 和奇数个 1
符号表示	EE	EO	OE	OO

初始状态：空二进制串即0个0，0个1即EE

触发状态切换的动作：输入一个字符

状态机模型：

1 动态规划与搜索 - 图1

状态转换：图中EE状态的字符，新增1个1则变为EO

接受状态：EO(即所有输入处理完后是接受状态即偶数个0奇数个1，则FSM处理成功，否则失败)

注意：不要把状态与状态切换的动作搞混

解题步骤

step1:定义所有可能状态
step2:对于当前时刻的每个状态，判断其能够由上个时刻的状态转移过来，写出状态转移方程
step3:初始化状态，并迭代推出最终结果。

股票买卖 V

import java.util.*;
class Main{
    /*
       状态机设计
       0 不持有股票非冷冻期
       1 持有股票
       2 不持有股票的冷冻期
       0 -> 0  
       0 -> 1
       1 -> 2
       1 -> 1
       2 -> 0
       dp[i][0] = max(dp[i-1][0],dp[i-1][2])
       dp[i][1] = max(dp[i-1][0]-w,dp[i-1][1])
       dp[i][2] = dp[i-1][1]+w
    }
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0;i < n;++i){
            nums[i] = sc.nextInt();
        }
        int[][] dp = new int[n+1][3];
        dp[0][0] = 0;
        dp[0][1] = -100000;
        dp[0][2] = -100000;
        for(int i = 1;i <= n;++i){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);
            dp[i][1] = Math.max(dp[i-1][0]-nums[i-1],dp[i-1][1]);
            dp[i][2] = dp[i-1][1] + nums[i-1];
        }
        int res = Math.max(dp[n][0],Math.max(dp[n][1],dp[n][2]));   // 注意三个状态都有可能
        System.out.println(res);
    }
}

股票买卖 IV

import java.util.*;
import java.io.*;
class Main{
    /*
       0    1
       不持有 持有
       0 -> 1   dp[i][k][1] = dp[i-1][k][0]-w
       0 -> 0   dp[i][k][0] = dp[i-1][k][0]
       1 -> 0   dp[i][k][0] = dp[i-1][k-1][1]+w
       1 -> 1   dp[i][k][1] = dp[i-1][k][1]
       dp[i][k][]到第i天位置，不超过k次交易，不持有/持有股票的最大值
    */
    public static void main(String[] args) throws NumberFormatException, IOException{
        BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));
        String[] strs = buf.readLine().split(" ");
        int N = Integer.parseInt(strs[0]);
        int k = Integer.parseInt(strs[1]);
        String[] nstrs = buf.readLine().split(" ");
        int[] nums = new int[N];
        for(int i = 0;i < N;++i){
            nums[i] = Integer.parseInt(nstrs[i]);
        }
        int[][][] dp = new int[N+1][k+1][2];
        for(int j = 0;j <= k;++j){             // 不可达状态
            dp[0][j][1] = -0x3f3f3f3f;
        }
        dp[0][0][0] = 0;
        for(int i = 1;i <= N;++i){
            for(int j = 0;j <= k;++j){
                dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j][0]-nums[i-1]);
                dp[i][j][0] = dp[i-1][j][0];
                if(j >= 1)
                    dp[i][j][0] = Math.max(dp[i][j][0],dp[i-1][j-1][1]+nums[i-1]);
            }
        }
        int res = Math.max(dp[N][k][0],dp[N][k][1]);
        System.out.println(res);
        buf.close();
    }
}

定义了m+1个状态
f[i][j]表示已经读取i个字符且到达KMP的第j个状态的字符串数目
任意一个不包含T的子串等价于走不到状态m。
每输入一个字符可以对应K
f[i][j]可不可以这么理解:i是状态机上走的步数，j是具体走到哪里。对于当前的位置j,每次走一步的结果，要么走到下一个位置（即原串和匹配串相等）要么回退（返回到0或原串和字符串相等的位置）

状压DP

状态压缩DP分成两大类：
1)棋盘式DP
2)集合式DP

棋盘式

小国王

在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。
基本思路：
状态表示： f[i][j][s]表示第i行已经放了j个棋子，最后一行的状态为s的方案数
step1:确定集合以及集合的属性
    集合（方案数进行分类):所有只摆在前i行，已经摆了j个国王，且第i行摆放的状态是s的所有方案数目
    属性：方案数目
step2:状态计算
如何枚举每一层的状态？
要求：
1）第i-1行与第i行之间也不能相互攻击到。
2）第i行内部不能有两个相邻1
==================================
对于要求1)可以转换为位运算(用整型变量a,b表示第i-1行和i行的状态):
条件1)等价于 (a&b) == 0 并且（a || b）不能有连续的1
已经摆了前i行，使用了j个国王，并且第i行的状态是a  =  已经摆了前i-1行，使用了j-count(a)个国王,并且第i-1排状态是b的方案数目
即 dp[i][j][a] = dp[i-1][j-count(a)][b]
时间复杂度：状态数目*状态计算的时间

编码实现步骤：

step1:保存所有合法状态
step2:获取所有合法状态中每个状态可转移的状态集合
step3:状态转移求出方案数目

实现

import java.util.*;
class Main{
    /*判断变量的二进制中是否有相邻的1，没有返回true
      如果存在相邻，则是非法状态，返回false,否则返回true
    */
    static boolean check(int s){
        return (s&(s >> 1)) == 0;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        /*每一行国王摆放不同的状态数目最大值，棋盘的最大长度为10，
          每个格子可以放国外也可以不放则最多方案数目为 2^10, 这里设置为 2^10+20留有余量
          显然2^10摆放方案中有很多不合法的摆放
        */
        int stateNum = (1 << 10)+20;     
        long[][][] dp = new long[12][110][stateNum];
        int[] cnt = new int[stateNum];    // 每个状态对应的二进制1的个数即国王的个数
        //step1:二进制枚举单层所有的摆放方案，并保存合法的摆放方案
        ArrayList<Integer> state = new ArrayList<>();
        for(int s = 0;s < (1 << n);++s){       // 二进制枚举状态范围为[0,2^n-1]
            if(check(s)){                      // 国王摆放是否合法，对于单行数据只要确保两个国外不相邻即可，即
                state.add(s);
                cnt[s] = Integer.bitCount(s);  // 存储当前合法状态所用棋子个数
            }
        }
        /*
            step2:选出每个状态能够存储的合法状态并存储,
                  head[s1]中存储的是s1能够转移到的状态集合
                  即s1和集合中的任意状态是棋盘上合法的相邻状态
            假设状态a,b,a与b从行来看都是合法状态，之前已经保存了所有状态
            a与b要如何是合法的相邻状态？
            满足：a&b == 0 并且  a || b 不存在相邻的1
        */
        //用于保存每个状态对应的合法转移状态集合
        ArrayList<Integer>[] heads = new ArrayList[stateNum];
        for(int i = 0;i < stateNum;++i) heads[i] = new ArrayList<>();
        for(int i = 0;i < state.size();++i){
            for(int j = 0;j < state.size();++j){
                int s1 = state.get(i);
                int s2 = state.get(j);
                if((s1&s2) == 0 && check(s1|s2)){
                    heads[i].add(j);         // 存储坐标，不直接存储状态值
                }
            }
        }
        /*
           step3:进行状态转移统计统计方案住
           dp[i][j][s]:使用j个国王摆了i行，最后一行状态为s的方案数目
           时间复杂度估算: 行数*棋子个数*合法状态数目*状态计算代价
            < 10*100*合法状态数目*每个状态可转移的状态个数 约等于 1.365 x 10^6
           合法状态并没有想象那么多。
        */
        dp[0][0][0] = 1;    /*初始化摆放0行各个状态*/
        for(int i = 1;i <= n+1;++i){
            for(int j = 0;j <= k;++j){
                /*枚举第i行的合法状态，对于每个状态,i-1行有多个合法的状态可以转移过来*/
                for(int a = 0;a < state.size();++a){            
                    for(int b = 0;b < heads[a].size();++b){   
                        /*状态转移:i行的s1 <- i-1行状态集合(s2)*/
                        int s1 = state.get(a);
                        int s2 = heads[a].get(b);
                        if(j >= cnt[s1]){     // 当前国王数目够用才能转移
                            dp[i][j][a] += dp[i-1][j-cnt[s1]][s2];
                        }
                    }
                }
            }
        }
        System.out.println(dp[n+1][k][0]);  // 摆放n+1行国王用了k个棋子最后一行不摆放棋子就是答案
    }
}

327 玉米田

数位DP

问题特点

题目特点：求区间[x,y]满足特定性质的元素个数
-------------------------------------------------------------------------
解决思路的关键点：
技巧1： [x,y] => f(y)-f(x-1)     (前缀和)
问题转换为： 区间[1,y]的满足性质的元素个数-区间[1,x-1]满足性质的元素个数  
------------------------------------------------------------------------
技巧2：利用树的结构来考虑（按位分类讨论）

模型分析

$1 动态规划与搜索 - 图2$

每个位置的数字的值都是有限定范围的，记为a，可选的值x在[0,a]范围内，因此可以分为两种情况讨论:
1）x = a
2) x < a

度的数量

问题:求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K 个互不相等的 B 的整数次幂之和。
实例：X=15,Y=20,K=2,B=2 ，则有且仅有下列三个数满足题意：
17=2^4+2^0
18=2^4+2^1
20=2^4+2^2

import java.util.*;
/*
  题目要求: 给定B进制数的范围,请该范围内的数目满足以下要求的数字个数:
  1)由0和1组成
  2)1的个数恰好为K个
  记[X-1,Y]的B进制范围表示为[x,y]
  原问题等价于求  [1,y]范围内满足要求的数 - [1,x]范围内满足要求的数
*/
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int X = sc.nextInt(),Y = sc.nextInt();
        int K = sc.nextInt(),B = sc.nextInt();
        // step1:组合计算结果打表
        int[][] comb = new int[33][33];   // 各个进制下数据的长度不会超过32位
        for(int i = 0;i < 33;++i){
            for(int j = 0;j <= i;++j){
                comb[i][j] = j == 0 ? 1 : comb[i-1][j] + comb[i-1][j-1];
            }
        }
        // step2:将X,Y转换为B进制数组，低位在前
        int[] nums1 = convert(X-1,B);
        int[] nums2 = convert(Y,B);
        int res = count(nums2,K,comb) - count(nums1,K,comb);
        System.out.println(res);
    }
    static int[] convert(int v,int B){
        List<Integer> list = new ArrayList<>();
        while(v > 0){
            list.add(v%B); v = v/B;
        }
        int[] res = list.stream().mapToInt(Integer::valueOf).toArray();
        return res;
    }
    /*
      求[1,x]范围内在满足题目要求的数字个数(从树的角度进行讨论)
      对于B进制数arr（共n位），从最高位（第n位）开始遍历每1位，对于第i位,cur表示已经取到的1的个数。
      第i位上的数字x有三种情况：
        1；当前位为大于1时：
            这位可以取0，那么满足条件的方案数为就是剩下位中取k-cur个1；
            这位可以取1, 那么满足条件的方案数为就是剩下位中取k-cur-1个1
        2：当这位是1时， 
              方案数目等于为0的方案数目(剩下位中取k-cur个1)
            + 设置为1后(++cur)，后续循环的方案数目
        3：当这位是0时， 这位只能取0， 那么只能看下一位的,循环继续
    */
    static int count(int[] arr,int K,int[][] comb){
        int len = arr.length;
        int ans = 0,cur = 0;           // 方案数目,1的个数
        for(int i = len-1;i >= 0;--i){ // 从高位开始遍历
            if(arr[i] > 1){            // 情况1
                if(K-cur >= 0) ans += comb[i][K-cur];     // 取0
                // 当前位大于1,并设置为1的时候，方案数目等于 从剩余i位中选择K-1-cur个数
                if(K-1-cur >= 0) ans += comb[i][K-1-cur]; // 取1  
                break;        // !!!!!!!!!!
            }else if(arr[i] == 1){     // 情况2
                if(K-cur >= 0) ans += comb[i][K-cur]; // 取0
                ++cur;                                // 取1
                if(cur > K) break;                    // 后续都不满足
            }
            if(i == 0 && cur == K) ++ans;              // 特殊情况
        }
        return ans;
    }
}

树形DP

注意这里的树并非特指二叉树，而是更加广义的树，满足n个节点并且节点之间仅仅存在1条边，即n-1条边

力扣的树形DP题目(二叉树)_

多叉树的树形DP

此处最长路径的定义：路径中边的数量最多

基本思路：

树的直径思路：
step1:任取一点作为起点，找到距离该点最远的一个点u。（DFS,BFS）
step2:再找到距离u最远的一点v,DFS,BFS
则u,v之间的路径就是一条直径。
==========================================================================
按照类别枚举所有直径。
分类依据：每个路径都有一个最高点，如果两个路径的最高点相同，那么这两条路径就是同类路径。
基本步骤：
step1:枚举树中每个点。
step2:找到这个点代表的一类路径的最大值。
问题：如何找到这个点代表的路径最大值？
基本思路：找到从该节点出发向下的所有路径的最大值与次大值即
    该点代表的一类路径最大值 = 从该点出发的所有向下路径的最大值与次大值
如何保证搜索的路径时向下的？
策略1：将访问当前节点之间的一个节点（父节点）传入，搜索时不重复搜索当前节点的父节点
原问题：多叉树种的最长路径
原问题拆解为子问题：包含当前节点且当前节点是路径的最高处的所有路径最大值
子问题：
1）保存从当前节点出发的所有向下路径的最大值与次大值，从而计算子节点为路径最高点的所有的路径提供的最大贡献（或者说子节点为根节点的路径最大值）
2）提供当前节点为其父亲节点为根节点的树提供的最大贡献。
注意：这里最大贡献的值 不是  子问题的值 而是  树的多侧所能提供的最大路径 ！！！！！！

核心思想：子节点更新父节点信息

实现

import java.util.*;
class Main{
    static int[] element;   // 链表节点值
    static int[] np;        // 单链表相邻节点地址
    static int[] heads;     // 单链表头
    static int[] w;         // 链表节点边值
    static int idx = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int N = n*2+10;
        element = new int[N];
        np = new int[N];
        heads = new int[N];
        w = new int[N];
        Arrays.fill(heads,-1);    // dummy node指向为空
        for(int i = 0;i < n-1;++i){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int v = sc.nextInt();
            add(a,b,v); add(b,a,v);
        }
        dfs(1,-1);
        System.out.println(res);
    }
    /*head[a]->b->-1(头插法)*/
    static void add(int a,int b,int v){
        element[idx] = b;
        w[idx] = v;
        np[idx] = heads[a];
        heads[a] = idx;
        ++idx;
    }
    /*返回从src出发向下最长路径和，把src节点提起来*/
    static int res = 0;
    static int dfs(int src,int father){
        int sum = 0;
        int subMax1 = 0,subMax2 = 0;      // 最大和次大路径和
        for(int next = heads[src];next != -1;next = np[next]){
            int node = element[next];
            int weight = w[next];
            if(node == father)
                continue;
            int dis = dfs(node,src) + weight;
            if(dis > subMax1) {           
                subMax2 = subMax1;
                subMax1 = dis;
            }else if(dis > subMax2){
                subMax2 = dis;
            } 
        }
        res = Math.max(res,subMax1+subMax2);
        // System.out.println(subMax1);
        return subMax1;
    }
}

3760 最大剩余油量

基本思路：

直观想法就是枚举树中所有路径，枚举方式，分类枚举。
分类依据：每个路径都有一个最高点，如果两个路径的最高点相同，那么这两条路径就是同类路径。
该点代表的一类路径最大值 = 从该点出发的所有向下路径的最大值与次大值 即 包含该点的油量最大值 = 从该点出发的所有向下路径的油量的最大值与次大值
注意：此题解法上类似于1072，这种枚举方式能够确保考虑到所有路径情况。

实现

import java.util.*;
class Solution{
    int[] ele;   // 节点编号存储
    int[] val;   // 链表节点的节点值存储
    int[] wgh;   // 链表节点的边的权重存储
    int[] np;    // next point
    int[] hds;   // 链表节点头指针维护
    int idx;
    Solution(){}
    void solve(){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int N = n*2;
        val = new int[n+1];   // id->节点值
        hds = new int[n+1];   // 邻接表
        ele = new int[N];     
        wgh = new int[N];
        np = new int[N];
        idx = 0;
        Arrays.fill(hds,-1);
        for(int i = 1;i <= n;++i){
            val[i] = sc.nextInt();
        }
        /*建立多叉树*/
        for(int i = 0;i < n-1;++i){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int w = sc.nextInt();
            add(a,b,w); add(b,a,w);
        }
        downDFS(1,-1);
        System.out.println(res);
    }
    // 分配一个节点并头插法插入到a节点的链表中
    void add(int a,int b,int w){
        ele[idx] = b;
        wgh[idx] = w;
        np[idx] = hds[a];
        hds[a] = idx;
        ++idx;
    }
    // 自顶向下枚举每个节点，当前节点的最大值 =  子节点的最大值+子节点的次大值+当前节点值
    long res = 0;
    long downDFS(int src,int father){
        long maxv1 = 0,maxv2 = 0;
        // 遍历该节点的邻接链表
        for(int next = hds[src];next != -1;next = np[next]){
            int nodeId = ele[next];
            int edgeWeight = wgh[next];
            if(nodeId == father) continue;
            long sum = downDFS(nodeId,src)-edgeWeight;
            if(sum < 0) continue;       // 油量贡献 < 0，跳过
            if(sum > maxv1){
                maxv2 = maxv1; maxv1 = sum;
            }else if(sum > maxv2){
                maxv2 = sum;
            }
        }
        /*包含当前节点的所有路径的最大剩余油量 = 左贡献最大油量+右最大贡献油量+节点值*/
        res = Math.max(maxv1+maxv2+val[src],res); 
        /*返回包含当前城市的所有向下路径的剩余的最大油量*/       
        return maxv1+val[src];                            
    }
}
class Main{
    public static void main(String[] args){
        new Solution().solve();
    }
}

1073 树的中心

基本思路：

1 动态规划与搜索 - 图3

树的中心：距离该节点的最远节点的路径的边是所有节点中最少的。

step1（子节点更新父节点信息）:通过一次dfs，我们可以获得每个节点的向下路径的最大值与次大值以及最大值路径的节点。
对于图中的每个节点存储三类信息：
1）当前节点出发向下路径的最大值
2）当前节点出发向下路径的次大值
3）当前节点出发向下路径的最大值经过的邻居节点。
step2（父节点信息更新子节点信息）:二次dfs,注意此次dfs搜索的顺序与第一次dfs要完全一致，我们需要利用之间存储的三类信心求向上路径的最大值。
当前节点的最大值 = max(父节点向上路径最大值，父节点向下路径（最大||次大）值) +   当前节点到父节点的边的权重
其中父节点向上路径最大值在遍历的过程中进行记录。
============================================================================================
情况1：父节点向下路径最大值不经过当前节点：
            当前节点的最大值 = max{父节点向下路径的最大值,父节点向上路径最大值}  +   当前节点到父节点的边的权重
情况2：父节点向下路径的最大值经过当前节点（如果使用最大值就是重复计算父节点与当前节点边的权重）
     当前节点的最大值 = {父节点向下路径的次大值,父节点向上路径最大值}  +   当前节点到父节点的边的权重
======================================================================================
注意：本题没有考虑负权重，如果有负权重则需要考虑边界情况

核心思想：子节点更新父节点信息存储，父节点更新子节点信息综合使用。

import java.util.*;
class Main{
    static int[] ele;    // element
    static int[] np;     // next pointer
    static int[] wht;    // weight(注意题目中没有负权值,有负权值需要根据题意调整)
    static int[] hds;     // heads
    static int idx = 0;
    static int INF = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int N = n*2+10;
        ele = new int[N];
        np = new int[N];
        wht = new int[N];
        hds = new int[n+1];
        Arrays.fill(hds,-1);
        for(int i = 0;i < n-1;++i){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int w = sc.nextInt();
            add(a,b,w); add(b,a,w);
        }
        downMax1 = new int[n+1];
        downMax2 = new int[n+1];
        upMax = new int[n+1];
        neighbour = new int[n+1];
        Arrays.fill(downMax1,INF);
        Arrays.fill(downMax2,INF);
        Arrays.fill(upMax,INF);
        dfs_down(1,-1);
        dfs_up(1,-1);
        int res = Integer.MAX_VALUE;
        for(int i = 1;i <= n;++i){
            int val = Math.max(downMax1[i],upMax[i]);     // 以当前节点为出发点到其他节点的最大值
            // System.out.printf("%d %d %d %d\n",i,downMax1[i],downMax2[i],upMax[i]);
            res = Math.min(res,val);
        }
        System.out.println(res);
    }
    static void add(int a,int b,int w){
        ele[idx] = b;
        wht[idx] = w;
        np[idx] = hds[a];
        hds[a] = idx;
        ++idx;
    }
    /*当前节点向下路径最大值，次大值，以及最大值经过的节点
      显然对于叶节点没有向下路径
    */
    static int[] downMax1;
    static int[] downMax2;
    static int[] neighbour;
    static int dfs_down(int src,int father){
        int max1 = 0,max2 = 0;
        for(int next = hds[src];next != -1;next = np[next]){
            int node = ele[next];
            int w = wht[next];
            if(node == father) continue;
            int dis = dfs_down(node,src)+w;
            if(dis > max1){
                max2 = max1; max1 = dis;
                downMax1[src] = max1; neighbour[src] = node; downMax2[src] = max2;
            }else if(dis > max2){
                max2 = dis;
                downMax2[src] = max2;
            }
        }
        return max1;
    }
    /*当前节点向上路径的最大值,根据第一次dfs获取的信息求取
      显然对于根节点（搜索起点）没有向上路径
    */
    static int[] upMax;      
    static void dfs_up(int src,int father){
        for(int next = hds[src];next != -1;next = np[next]){
            int node = ele[next];
            int w = wht[next];
            if(node == father) continue;
            // 利用父节点去更新每个子节点的向上路径最大值
            if(neighbour[src] == node){
                upMax[node] = Math.max(downMax2[src],upMax[src])+w;
            }else{
                upMax[node] = Math.max(downMax1[src],upMax[src])+w;
            }
            dfs_up(node,src);
        }
    }
}

1075 数字转换

a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数

基本思想：树的建立

节点：数字，边：其中一个数字的约数之和等于另外一个数字

目标：树的最长路径，路径中节点的最大值不超过N。

import java.util.*;
class Tree{
    int[] e;
    int[] np;
    int[] h;
    int idx = 0;
    Tree(int N){
        e = new int[N];
        np = new int[N];
        h = new int[N];
        Arrays.fill(h,-1);
    }
    void add(int a,int b){
        e[idx] = b; np[idx] = h[a]; h[a] = idx; ++idx;
    }
}
class Main{
    static int res = 0;      
    static int dfs(Tree tree,int src,int father){
        int max1 = 0,max2 = 0;
        for(int next = tree.h[src];next != -1;next = tree.np[next]){
            int id = tree.e[next];
            if(id == father) continue;
            int val = dfs(tree,id,src)+1;
            if(val > max1){
                max2 = max1;max1 = val;
            }else if(val > max2){
                max2 = val;
            }
        }
        res = Math.max(res,max1+max2);  // 求取最长直径
        return max1;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Tree tree = new Tree(n*2);   // 数据容量确保存储所有边即可
        /*step1:统计每个数组对应的约数之和
          正向思维：对每个数据求其所有约数，然后相加求和       O(n* 根号n) 
          逆向思维: 对于每个数看他是哪些数的约数，进行累加求和 O(nlog级别)
        */
        int[] cnt = new int[n+1];         // 存储每个数的约数之和
        for(int i = 1;i <= n;++i){        // 枚举数i
            for(int j = 2;j <= n/i;++j){  // i是i*j的约数（这里需要注意j从2开始，因为1不是本身的约数）
                cnt[i*j] += i;
            }
        }
        /*
          step2:建立无向图
          这里的无向图本质上是森林的集合
        */
        boolean[] isTreeNode = new boolean[n+1];
        for(int i = 1;i <= n;++i){
            if(cnt[i] > 0 && i > cnt[i]){
                tree.add(i,cnt[i]);
                tree.add(cnt[i],i);
                isTreeNode[i] = true;   // 只需要标记一个即可，避免重复搜索
            }
        }
        /*
           包含最大直径的树一定含有节点1，因此直接从1开始搜索,避免超时
           step3:求取树的最大直径
        */
        dfs(tree,1,-1);
        System.out.println(res);
    }
}

搜索

Flood Fill思想

本质上是BFS/DFS搜索，注意： 1）越界问题 2）重复访问问题（BFS入队标记，不要采用出队标记） 即可。

池塘计数

import java.util.*;
class Main{
    static boolean[][] vis;
    static String[] map;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(),M = sc.nextInt();
        vis = new boolean[N][M]; map = new String[N];
        for(int i = 0;i < N;++i) map[i] = sc.next();
        int cnt = 0;
        for(int r = 0;r < N;++r){
            for(int c = 0;c < M;++c){
                if(bfs(r,c)) ++cnt;
            }
        }
        System.out.println(cnt);
    }
    /*通过BFS进行Flood Fill*/
    public static boolean bfs(int r,int c){
        if(vis[r][c] || map[r].charAt(c) != 'W') return false;
        int row = map.length,col = map[0].length();
        Queue<int[]> q = new ArrayDeque<>(); 
        q.offer(new int[]{r,c});
        vis[r][c] = true;
        while(!q.isEmpty()){
            int[] t = q.poll();
            for(int i = -1;i <= 1;++i){
                for(int j = -1;j <= 1;++j){
                    int rr = t[0] + i,cc = t[1] + j;
                    if(rr >= 0 && rr < row && cc >= 0 && cc < col && !vis[rr][cc] && map[rr].charAt(cc) == 'W'){
                        q.offer(new int[]{rr,cc});
                        vis[rr][cc] = true;
                    }
                }
            }
        }
        return true;
    }
}

城堡问题

import java.util.*;
class Main{
    static boolean[][] vis;
    static int[][] map;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(),n = sc.nextInt();
        vis = new boolean[m][n]; map = new int[m][n]; 
        for(int r = 0;r < m;++r){
            for(int c = 0;c < n;++c){
                map[r][c] = sc.nextInt();
            }
        }
        int cnt = 0;
        int area = 0;
        for(int r = 0;r < m;++r){
            for(int c = 0;c < n;++c){
                int tmp = bfs(r,c);
                if(tmp > 0){
                    ++cnt;
                    area = Math.max(tmp,area);
                } 
            }
        }
        System.out.println(cnt);
        System.out.println(area);
    }
    /*通过BFS进行Flood Fill*/
    // 西 北 东 南
    static int[] dr = {0,-1,0,1};
    static int[] dc = {-1,0,1,0};
    public static int bfs(int r,int c){
        if(vis[r][c]) return 0;
        int row = map.length,col = map[0].length;
        Queue<int[]> q = new ArrayDeque<>(); 
        q.offer(new int[]{r,c});
        vis[r][c] = true;
        int area = 1;
        while(!q.isEmpty()){
            int[] t = q.poll();
            int rr = t[0],cc = t[1];
            int val = map[rr][cc];
            for(int i = 0;i < 4;++i){
               int nr = rr + dr[i],nc = cc + dc[i];
               if(nr >= 0 && nr < row && nc >= 0 && nc < col){
                   if(((val >> i) & 1) != 1 && !vis[nr][nc]){    // 当前方向没有墙且没有fill
                       q.offer(new int[]{nr,nc});
                       vis[nr][nc] = true;
                       ++area;
                   }
               }
            }
        }
        return area;
    }
}

山峰和山谷

import java.util.*;
class Main{
    static boolean[][] vis;
    static int[][] map;
    /*
       基本思路：BFS的Flood Fill
       注意：标志位的设计非常巧妙
    */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        vis = new boolean[n][n]; map = new int[n][n];
        for(int r = 0;r < n;++r){
            for(int c = 0;c < n;++c){
                map[r][c] = sc.nextInt();
            }
        }
        int peek = 0,bottom = 0;
        for(int r = 0;r < n;++r){
            for(int c = 0;c < n;++c){
                if(!vis[r][c]){                // 访问的格子不再访问，不要放入子函数判断
                    boolean[] res = bfs(r,c);
                    if(!res[0]) ++peek;
                    if(!res[1]) ++bottom;
                }
            }
        }
        System.out.printf("%d %d\n",peek,bottom);
    }
    /*通过BFS进行Flood Fill*/
    public static boolean[] bfs(int sr,int sc){
        /*标志位: 是否存在比当前格子高的山峰，是否存在比当前格子矮的山峰 */
        boolean[] res = new boolean[2];     
        int row = map.length,col = map[0].length;
        Queue<int[]> q = new ArrayDeque<>(); 
        q.offer(new int[]{sr,sc});
        vis[sr][sc] = true;
        while(!q.isEmpty()){
            int[] t = q.poll();
            int r = t[0],c = t[1];
            for(int i = -1;i <= 1;++i){
                for(int j = -1;j <= 1;++j){
                    if(i == 0 && j == 0) continue;
                    int rr = i + r,cc = j + c;
                    if(rr < 0 || rr >= row || cc < 0 || cc >= col) continue;
                    if(map[rr][cc] > map[r][c]) res[0] = true;            // 相邻格子存在比当前高的山峰
                    else if(map[rr][cc] < map[r][c]) res[1] = true;       // 相邻格子存在比当前矮的山峰
                    else if(!vis[rr][cc]){
                        q.offer(new int[]{rr,cc});
                        vis[rr][cc] = true;
                    }
                }
            }
        }
        return res;
    }
}