动态规划 4
-
【题解】求m区间内的最值(ST表实现)
求m区间内的最小值题目描述一个含有 nnn 项的数列,求出每一项前的 mmm 个数到它这个区间内的最小值。若前面的数不足 mmm 项则从第 111 个数开始,若前面没有数则输出 000。输入格式第一行两个整数,分别表示 nnn,mmm。第二行,nnn 个正整数,为所给定的数列 aia_iai。输出
-
最近公共祖先LCA(倍增思想)
定义最近公共祖先简称LCA(Lowest Common Ancestor)。两个节点的最近公共祖先指的是这两个点的公共祖先中离根最远的那个。
-
悬线法处理最大子矩阵问题
适用场景可用于求解给定矩阵中满足某条件的极大矩阵(最大子矩阵)。设矩阵为N×MN\times MN×M ,算法复杂度为O(N×M)O(N\times M)O(N×M) 。悬线法思想及实现若在一个矩形区域内寻找满足某条件的最大子矩阵。