精华内容
下载资源
问答
  • 2018-07-16 12:14:00

    转载于:https://www.cnblogs.com/xuebajunlutiji/p/9317062.html

    更多相关内容
  • 已知向量$\textbf{a},\textbf{b}$满足:$|\textbf{a}|=|\textbf{b}|=1,\textbf{a}\cdot\textbf{b}=\dfrac{1}{2},\textbf{c}=(m,1-m),\textbf{d}=(n,1-n),(m,n\in R)$,存在$\textbf{a},\textbf{b}$,对于任意的实数$m,n...

    已知向量$\textbf{a},\textbf{b}$满足:$|\textbf{a}|=|\textbf{b}|=1,\textbf{a}\cdot\textbf{b}=\dfrac{1}{2},\textbf{c}=(m,1-m),\textbf{d}=(n,1-n),(m,n\in R)$,
    存在$\textbf{a},\textbf{b}$,对于任意的实数$m,n$,不等式$|\textbf{a}-\textbf{c}|+|\textbf{b}-\textbf{d}|\ge T$ 恒成立,则$T$的取值范围_____


    解析:设$\textbf{a}=\overrightarrow{OA},\textbf{b}=\overrightarrow{OB},\textbf{c}=\overrightarrow{OC},\textbf{d}=\overrightarrow{OD}$,
    由题意$A,B$在单位圆上运动,且$\angle AOB=\dfrac{\pi}{3}$.$C,D$在$x+y-1=0$上运动.
    由题意只需$T\le \max\limits_{A,B}\{\min\limits_{C,D}\{|AC|+|BD|\}\}$.
    方法一:几何意义,先固定$A,B$,则$AC\perp CD,BD\perp CD$时取得$\min\limits_{C,D}(|AC|+|BD|)$,
    再取$A,B$中点$M$;$C,D$ 中点$N$,故$\min\limits_{C,D}(|AC|+|BD|)=2|MN|$,作$OE\perp CD$,连接$OM$,则当$A,B$动起来时$MN\le OM+OE=\dfrac{\sqrt{3}+\sqrt{2}}{2}$,故$T\le \sqrt{3}+\sqrt{2} $
    方法二:设$A(cos \theta,sin\theta),B(\cos(\theta+\dfrac{\pi}{3}),sin(\theta+\dfrac{\pi}{3})),$
    设$d=\dfrac{|cos\theta+sin\theta-1|}{\sqrt{2}}+\dfrac{|cos(\theta+\dfrac{\pi}{3}+\sin(\theta+\dfrac{\pi}{3})-1|}{\sqrt{2}}$
    题目转换为存在$\theta$对$T\le d $成立,即$T\le d_{max}$
    $$\dfrac{|cos\theta+sin\theta-1|}{\sqrt{2}}+\dfrac{|cos(\theta+\dfrac{\pi}{3})+\sin(\theta+\dfrac{\pi}{3})-1|}{\sqrt{2}}=\dfrac{1}{\sqrt{2}}*\max$$

    \begin{equation*}
    \{|cos\theta+sin\theta+cos(\theta+\frac{\pi}{3})+\sin(\theta+\frac{\pi}{3})-2|,|cos\theta+sin\theta-cos(\theta+\frac{\pi}{3})-\sin(\theta+\frac{\pi}{3})| \}
    \end{equation*}

    $$=\dfrac{\max\{|\sqrt{6}sin(\theta+\phi_1)-2|,|\sqrt{2}sin(\theta+\phi_2)|\}\le \sqrt{3}+\sqrt{2}}{\sqrt{2}}$$
    即$T\le\sqrt{3}+\sqrt{2}$

    转载于:https://www.cnblogs.com/mathstudy/p/10350106.html

    展开全文
  • RMQ 区间最值问题

    2021-09-19 23:25:33
    Range Minimum/Maximum Query问题描述搜索(暴力解)线段树稀疏表(ST)笛卡尔树 现在在HBUE读本科,小日子过的有点闲 就具体的来抓几个点,补补算法 问题描述 对于长度为 n 的数列 A,回答若干 (q次) 询问 RMQ(A, i,...


    现在在HBUE读本科,小日子过的有点闲
    就具体的来抓几个点,补补算法


    问题描述


    对于长度为n的序列A,回答若干(q次)询问RMQ(A, i, j)

    RMQ(A, i, j)需要返回序列由A[i]A[j]为端点,所构成的A的子段中的最大值。

    可参考 [牛客 NC50443]

    部分方法实现于这个 工具类

    多数源码的run方法细节被隐藏,需要完整可执行程序可直接跳转至 标准 RMQ

    如若出现如 < O 1 , O 2 > <O_{1},O_{2}> <O1O2> 这样的表达式,其意义是算法的预处理时间复杂度为 O 1 O_{1} O1,单次查询时间复杂度为 O 2 O_{2} O2


    朴素算法


    public class Main {
    
        public int RMQ(int[] A, int i, int j) {
            int ans = Integer.MIN_VALUE;
            while (i <= j)
                ans = Math.max(ans, A[i++]);
            return ans;
        }
    }
    

    < O ( 0 ) , O ( ∣ i − j ∣ ) > <O(0),O(|i - j|)> <O(0)O(ij)>

    暴力的不谈。


    线段树


    public class Main {
    
        public class RMQ {
    
            Node root;
    
            RMQ(int[] A) {
                this.root = building(A, 0, A.length - 1);
            }
    
            public int query(int i, int j) { return query(root, i, j); }
    
            public int query(Node root, int start, int end) {
                if (start <= root.start && end >= root.end) return root.val;
                int res = 0x80000000, mid = root.start + root.end >> 1;
                if (start <= mid) res = query(root.left, start, end);
                if (end > mid) res = max(res, query(root.right, start, end));
                return res;
            }
    
            private Node building(int A[], int start, int end) {
                if (start == end) return new Node(end, end, A[end]);
                Node node = new Node(start, end);
                node.left = building(A, start, start + end >> 1);
                node.right = building(A, start + end + 2 >> 1, end);
                return node.fresh();
            }
    
            private class Node {
    
                int val, start, end;
    
                Node left, right;
    
                Node(int start, int end) {
                    this.start = start;
                    this.end = end;
                }
    
                Node(int start, int end, int val) {
                    this.start = start;
                    this.end = end;
                    this.val = val;
                }
    
                Node fresh() {
                    this.val = max(getValue(this.left), getValue(this.right));
                    return this;
                }
    
                private int getValue(Node node) { return node == null ? Integer.MIN_VALUE: node.val; }
            }
        }
    }
    

    < O ( n log ⁡ n ) , O ( log ⁡ n ) > <O(n \log n),O(\log n)> <O(nlogn)O(logn)>

    纯纯的模板,不谈。


    单调栈


    注意:这是个 离线 算法。

    以序列A、查询Q为例:

    array array 1 7 3 4 2 5 A:    Q1 Q1 Q1->array:a0 Q1->array:a4 Q2 Q2 Q2->array:a3 Q2->array:a5 Q3 Q3 Q3->array:a2 Q3->array:a2

    我们将Q按右端点升序排列,遍历A,同时维护单调栈

    当遍历到的元素和待查询Q的右端点相同时,进行查询。

     forA[2]inA

    stack stack A[2] 3 A[1] 7 stack

    RMQ(2, 2) = 3,因为A[1]的下标越过了Q的左端点。

     -----------------

     forA[4]inA

    stack stack A[4] 2 A[3] 4 A[1] 7 stack

    RMQ(0, 4) = 7

     -----------------

     forA[5]inA

    stack stack A[5] 5 A[1] 7 stack

    RMQ(3, 5) = 5,因为A[1]的下标越过了Q的左端点。

    在这里,栈内元素也可以表示另一层含义。

    以完成遍历后栈的状态来表述:

    栈底元素A[1]代表原序列A[0, 1]的最大值。
    栈顶元素A[5]代表原序列A[2, 5]的最大值。

    正因如此,在完全压入查询子段包含的全部元素后,我们可以自底查找第一个映射原序列下标大于等于查询左端点的元素,这个元素就是子段的最值。

    import java.util.*;
    
    public class Main {
    
        public static void main(String[] args) { new Main().run(); }
    
        public void run() {
            answer = RMQ.of(A, Q);
        }
    
        public static class RMQ {
    
            public static int[] of(int[] A, List<Query> Q) {
                Queue<IndexQuery> query = new PriorityQueue();
                int N = A.length, M = Q.size();
                int[] stack = new int[N + 1];
                int[] answer = new int[M];
                for (int i = 0; i < M; i++)
                    query.add(new IndexQuery(i, Q.get(i)));
                for (int i = 0, top = 0; i < N; i++) {
                    while (top > 0 && A[stack[top]] <= A[i]) top--;
                    stack[++top] = i;
                    if (query.isEmpty()) return answer;
                    else
                        while (!query.isEmpty() && query.peek().j == i) {
                            IndexQuery now = query.poll();
                            answer[now.index] = A[stack[lowerBound(stack, 1, top - 1, now.i)]];
                        }
                }
                return answer;
            }
    
            private static int lowerBound(int[] A, int start, int length, int key) {
                while (length > 0) {
                    int half = length >> 1;
                    if (key > A[start + half]) {
                        start += half + 1;
                        length -= half + 1;
                    } else
                        length = half;
                }
                return start;
            }
    
            public static class Query {
    
                int i, j;
    
                Query(int i, int j) {
                    this.i = i;
                    this.j = j;
                }
            }
    
            private static class IndexQuery implements Comparable<IndexQuery> {
    
                int index, i, j;
    
                IndexQuery(int index, Query query) {
                    this.index = index;
                    if (query.i <= query.j) {
                        this.i = query.i;
                        this.j = query.j;
                    } else {
                        this.i = query.j;
                        this.j = query.i;
                    }
                }
    
                @Override
                public int compareTo(IndexQuery o) {
                    return this.j > o.j ? 1 : -1;
                }
            }
        }
    }
    

    虽然栈内每个元素最多进出一次,也就是我们整个栈的维护能在线性时间内完成,

    但根据上述例子我们可以看到,自底向上查找时,我们会频繁的扫描“赖在”栈底的元素,当原序列A单调递减,且查询区间长度均摊为1时,就算查询是均匀分布的,整个查询操作的复杂度可能会达到 O ( n 2 ) O(n^2) O(n2),最差情况下会将至 O ( q n ) O(qn) O(qn)

    为了避免极端情况下,算法的性能得不到保障,推荐将该查找步骤采用二分查找的方式实现。

    < O ( q log ⁡ q n ) , O ( 0 ) > <O(q \log qn),O(0)> <O(qlogqn)O(0)>

    万用结构单调栈。


    稀疏表

    Sparse Table


    对于一个查询:

    array array a1 a2 a3 a4 a5 a6 a7 a8 a9 A:    query query query->array:a1 query->array:a6

    我们总是能用一个长度为2^K的区间、或将两个长度为2^k的区间叠加,来完全覆盖它。

    array array a1 a2 a3 a4 a5 a6 a7 a8 a9 A:    query1 query1 query1->array:a1 query1->array:a5 query2 query2 query2->array:a2 query2->array:a6

    如图所示,我们能将长度为5的子段查询规格化为两个长度为2^2的子段的子查询,

    而长度为2^2的查询我们又能规划化为两个2^1的查询,

    直至查询对应原序列单个元素。

    也就是说,对于任意查询,我们都能化为: R M Q ( i , j ) = max ⁡ ( R M Q ( i , i + 2 k ) , R M Q ( j − 2 k , j ) ) , k = ⌊ log ⁡ 2 ( j − i ) ⌋ RMQ(i,j) = \max (RMQ(i,i + 2^k),RMQ(j - 2^k,j)),k=\lfloor \log_{2}(j - i)\rfloor RMQ(ij)=max(RMQ(ii+2k)RMQ(j2kj))k=log2(ji)查询的速度,直接和查询长度为二的幂的子段的速度挂钩。

    这里我们需要定义一下稀疏表所用到的ST的含义:

    ST[i][k]指以i为左端点、长度为2^k的子段的最大值。

    S T [ i ] [ k ] = max ⁡ ( A [ i , i + 2 k ) ) ST[i][k] = \max (A[i,i + 2^{k})) ST[i][k]=max(A[ii+2k))

    由此我们很容易得出ST[i][0] = A[i]

    此外我们再给出一个倍增公式: S T [ i ] [ k ] = max ⁡ ( S T [ i ] [ k − 1 ] , S T [ i + 2 k − 1 ] [ k − 1 ] ) , k ≥ 1 ST[i][k] = \max (ST[i][k-1],ST[i + 2^{k - 1}][k-1]) , k \geq1 ST[i][k]=max(ST[i][k1]ST[i+2k1][k1])k1它能让我们在 O ( n log ⁡ n ) O(n \log n) O(nlogn) 的时间复杂度下,完成长度为二的幂的子段的最值查询的初始化。

    但同时,它也需要有 O ( n log ⁡ n ) O(n \log n) O(nlogn) 的空间来存放预处理出的结果。

    public class Main {
    
        public static void main(String[] args) { new Main().run(); }
    
        public void run() {
        	r = RMQ.of(A);
            r.query(i, j);
        }
    
        public static class RMQ {
    
            public static RMQ of(int[] A) { return new RMQ(A); }
    
            public int query(int i, int j) {
                if (i > j) return query(j, i);
                int k = floorLog2(j - i);
                return max(ST[i][k], ST[j - (1 << k) + 1][k]);
            }
    
            private int[][] ST;
    
            RMQ(int[] A) {
                int N = A.length, M = floorLog2(N);
                ST = new int[N][M + 1];
                for (int i = 0; i < N; i++)
                    ST[i][0] = A[i];
                for (int k = 1; k <= M; k++)
                    for (int i = 0; i + (1 << k - 1) < N; i++)
                        ST[i][k] = max(ST[i][k - 1], ST[i + (1 << k - 1)][k - 1]);
            }
        }
    }
    

    稀疏表在处理RMQ问题时有点像动态规划,论其本质是倍增思想,也有叫什么逆二分、ST算法的。

    稀疏表,它稀疏就稀疏在,预处理的问题并不是问题的全集,但预处理出的问题可以以极小的代价组合出问题的全集。

    总之,好用。

    < O ( n log ⁡ n ) , O ( 1 ) > <O(n \log n),O(1)> <O(nlogn)O(1)>


    四毛子算法

    Method of Four Russians


    相较于算法,它更像是一种思想,暴力分块思想。

    拿稀疏表举例:

    对于一个长度为N的序列A,我们将其分成长度为KM块,并以长度为K的块为最小单元做倍增。

    不难发现其时间复杂化度为 O ( K N log ⁡ K N ) O(\frac{K}{N}\log\frac{K}{N}) O(NKlogNK),我们取 K = log ⁡ N 2 K = \cfrac{\log N}{2} K=2logN。此时 “块” 的稀疏表的初始化显然能在 O ( N ) O(N) O(N) 的复杂度下完成。

    对于块间的查询,现在我们能在 < O ( n ) , O ( 1 ) > <O(n),O(1)> <O(n)O(1)> 的意义下完成。

    并且在这种暴力分块下,
    显然存在一个隐性条件 K ≤ ⌈ log ⁡ N ⌉ ≤ 64 K\leq \lceil \log N \rceil \leq 64 KlogN64事实上 N ≥ 2 20 N \ge 2^{20} N220就实属难得了,Windows 10 专业工作站版支持的最大 RAM 也才 6 × 2 40   B y t e 6 \times 2^{40}\ Byte 6×240 Byte,而 2 64 2^{64} 264 32 32 32 位整形变量需要占用的内存达到了惊人的 2 68   B y t e 2^{68} \ Byte 268 Byte

    这也是下面将要介绍的两个算法的理论依据。

    那么现在的问题就是,查询发生在块内怎么办?


    约束 RMQ


    也有人称其为 ± 1 R M Q \pm 1 RMQ ±1RMQ

    若长度为N序列A满足对任意 i ∈ ( 2 , N ] i \in (2,N] i(2N],都有 ∣ A i − A i − 1 ∣ = 1 \left| A_{i} - A_{i - 1} \right| = 1 AiAi1=1,那么我们称其为约束序列。

    那么对于约束序列的区间最值问题,我们称为约束RMQ。

    由于约束序列的特殊性质,我们可以在不需要每个元素具体的值的情况,以很小的代价来表述它们的大小关系。

    对于约束序列

    array array 3 2 3 4 5 6 5 6 7 6 A:    s1 -1 s2 1 s3 1 s4 1 s5 1 s6 -1 s7 1 s8 1 s9 -1 array:a1->s1 array:a2->s2 array:a3->s3 array:a4->s4 array:a5->s5 array:a6->s6 array:a7->s7 array:a8->s8 array:a9->s9

    我们不关心每个元素的具体值,只把注意力放在元素与其左元素的差值上,并直接忽略掉左端点元素,我们用 1   /   0 1 \ / \ 0 1 / 0 表示 A i − A i − 1 = 1   / − 1 A_{i} - A_{i - 1} = 1 \ / -1 AiAi1=1 /1,并将其按二进制位从底到高保存到整形变量block当中。

    于是对于上述序列A,我们有状态block = 011011110

    现在我们可以假设原序列左端点为任意值,例如将其设为0,再按block描述的大小关系将其重构,于是能得到序列

    array array 0 -1 0 1 2 3 2 3 4 3 B:   

    构建出的序列的区间最值与原序列的区间最值的位置一一映射(只要你对于最值出现多个的情况采取相同的措施)。

    对于这样的序列,我们朴素的去枚举它的区间最值情况,时间复杂度在 O ( K 2 ) O(K^2) O(K2) O ( log ⁡ 2 N 4 ) O( \cfrac{\log ^{_2}N}{4}) O(4log2N),可能的block一共存在有 2 K − 1 2^{K-1} 2K1 种,枚举所以可能的block时间复杂度在 O ( 2 log ⁡ N − 2 log ⁡ 2 N 4 ) O(\cfrac{\sqrt{2^{\log N - 2}} \log ^{_2}N}{4}) O(42logN2 log2N),整理可得知,对于块间查询的预处理,我们能在 O ( n ) O(n) O(n) 意义下的时间复杂度下完成。

    public class Main {
    
        public static void main(String[] args) { new Main().run(); }
    
        public void run() {
            rmq = PlusOrMinusOneRMQ .of(A);
        }
    
        public static class PlusOrMinusOneRMQ {
    
            int N, M, K;
            int[][] ST;
            int[][][] F;
            int[] A, block;
    
            public static PlusOrMinusOneRMQ of(int[] A) { return new PlusOrMinusOneRMQ.of(A, 0.5); }
            
    		public static PlusOrMinusOneRMQ of(int[] A, double xK) { return new PlusOrMinusOneRMQ(A, xK); }
    
            PlusOrMinusOneRMQ(int[] A, double xK) {
                this.N = A.length;
                this.K = max(1, (int)(floorLog2(N) * xK));
                this.M = N / K;
                if (N % K > 0) M++;
                block = new int[M];
                F = new int[1 << K - 1][K][K];
                ST = new int[M][floorLog2(M) + 1];
                this.A = A;
                init();
            }
    
            public int query(int i, int j) {
                if (i > j) return query(j, i);
                int B1 = i / K, B2 = j / K;
                int O1 = i % K, O2 = j % K;
                if (B1 == B2)
                    return B1 * K + F[block[B1]][O1][O2];
                int LM = F[block[B1]][O1][K - 1] + B1 * K,
                        RM = F[block[B2]][0][O2] + B2 * K;
                int res = A[LM] < A[RM] ? LM : RM;
                if (B2 - B1 > 1) {
                    int k = floorLog2(B2 - B1 - 1);
                    int MLM = ST[B1 + 1][k], MRM = ST[B2 - (1 << k)][k];
                    int ans = A[MLM] < A[MRM] ? MLM : MRM;
                    if (A[ans] < A[res]) res = ans;
                }
                return res;
            }
    
            private void init() {
                int min, now, block, offset;
                for (int i = 0; i < M; i++) {
                    min = offset = i * K;
                    block = 0;
                    for (int k = 1; k < K && offset + k < N; k++)
                        if (A[offset + k] < A[offset + k - 1]) {
                            block |= 1 << k - 1;
                            if (A[offset + k] < A[min])
                                min = offset + k;
                        }
                    this.block[i] = block;
                    this.ST[i][0] = min;
                }
                for (int k = 1; k <= floorLog2(M); k++)
                    for (int i = 0; i + (1 << k - 1) < M; i++)
                        ST[i][k] = A[ST[i][k - 1]] < A[ST[i + (1 << k - 1)][k - 1]] ? ST[i][k - 1] : ST[i + (1 << k - 1)][k - 1];
                for (int k = 0, m = 1 << K - 1; k < m; k++)
                    for (int i = 0; i < K; i++) {
                        F[k][i][i] = i;
                        now = 0;
                        min = 0;
                        for (int j = i + 1; j < K; j++) {
                            F[k][i][j] = F[k][i][j - 1];
                            if ((k & (1 << j - 1)) == 0) now++;
                            else if (min > --now) {
                                F[k][i][j] = j;
                                min = now;
                            }
                        }
                    }
            }
        }
    }
    

    因为看到有人说 K = log ⁡ N ∗ 1.5 K = \log N * 1.5 K=logN1.5 算法的常数会更小。

    PlusOrMinusOneRMQ的构造方法中,设计了一个入参xK,用来控制K的系数。

    建议范围 0.5 - 1. 5。

    < O ( n ) , O ( 1 ) > <O(n),O(1)> <O(n)O(1)>


    状压 RMQ


    现在我们使用过单调栈求解了RMQ问题,又得知一个隐性条件 K ≤ 64 K \leq 64 K64,那么我们是否能将其结合起来,设计出一个高效的算法呢。

    在使用单调栈求解RMQ时,不难发现,栈元素能自底向上构成原序列的子序列,也就是栈内元素对应原序列的下标是呈单调的,并且对于块间在最坏情况下,栈内元素不会多于 64 64 64

    综上,我们只用一个整形变量,就可以把块内遍历到某一元素的单调栈的状态压缩,在查询时,根据栈的状态返回结果。

    对于单调栈的维护,显然能在 O ( n ) O(n) O(n) 的复杂度下完成,对于根据状态的查询,通过一套不依赖输入的位运算,也可以做到在 O ( 1 ) O(1) O(1) 复杂度的意义下完成。

    还是以单调栈时所用数据为例,对于序列A的查询Q,需要对状态还原到如下栈:

    array array 1 7 3 4 2 5 A:    stack A[2] A[1] 3 7 stack2 A[4] A[3] A[1] 2 4 7 stack3 A[5] A[1] 5 7 array:a2->stack array:a4->stack2 array:a5->stack3

    枚举遍历A的元素时,我们将序列A的元素下标与整形二进制表示下低到高位相对应,当元素在栈内时,使当前位置 1 1 1,反之置 0 0 0,于是有状态序列

    array array 000001b 000010b 000110b 001010b 011010b 100010b B:   

    对于查询RMQ(2, 2),我们将B[2]的低2位置0,此时从低位起,第一个1的位置,就映射着RMQ(2, 2)要查询到的结果的位置,即000100b的第2位。

    对于查询RMQ(0, 4)B[4]第一个1的位置,就映射着RMQ(0, 4)要查询到的结果的位置,即011010b的第1位。

    对于查询RMQ(3, 5),我们将B[5]的低3位置0,此时从低位起,第一个1的位置,就映射着RMQ(2, 2)要查询到的结果的位置,即100000b的第5位。

    这个过程和单调栈查询的过程如出一辙,不过在这里,我们用了极小的代价保存了全部的栈状态,这也使得算法可以在线完成。

    public class Main {
    
        public static class RMQ {
    
            int N, K;
            int[] A, B;
            int[][] ST;
    
            public static RMQ of(int[] A) { return RMQ.of(A, 0.5); };
    
            public static RMQ of(int[] A, double xK) { return new RMQ(A, xK); };
    
            RMQ(int[] A, double xK) {
                this.A = A;
                this.N = A.length;
                this.K = max(1, (int)(floorLog2(N) * xK));
                int n = N / K + (N % K == 0 ? 0 : 1);
                ST = new int[n][floorLog2(n) + 1];
                B = new int[N];
                init();
            }
    
            public int query(int i, int j) {
                if (i > j) return query(j, i);
                int ans = Integer.MIN_VALUE;
                int Si = i / K, Sj = j / K;
                if (Si == Sj)
                    return A[i + countTrailingZero(B[j] >> i % K)];
                if (Sj - Si > 1) {
                    int k = floorLog2(Sj - Si - 1);
                    ans = max(ST[Si + 1][k], ST[Sj - (1 << k)][k]);
                }
                return max(
                        ans,
                        A[Sj * K + countTrailingZero(B[j])],
                        A[i + countTrailingZero(B[Si * K + K - 1] >> i % K)]
                );
            }
    
            private void init() {
                int[] stack = new int[K + 1];
                int top = 0, c = 0;
                for (int i = 0, k = 0; i < N; k = 0, top = 0) {
                    while (k++ < K && i < N) {
                        if (i > 0) B[i] = B[i - 1];
                        if (k == 1) B[i] = 0;
                        while (top > 0 &&  A[i] > A[stack[top]])
                            B[i] ^= 1 << stack[top--] % K;
                        stack[++top] = i;
                        B[i++] |= 1 << k - 1;
                    }
                    ST[c++][0] = A[stack[1]];
                }
                for (int k = 1; k <= floorLog2(ST.length); k++)
                    for (int i = 0; i + (1 << k - 1) < ST.length; i++)
                        ST[i][k] = max(ST[i][k - 1], ST[i + (1 << k - 1)][k - 1]);
            }
        }
    }
    
    

    对于上述根据状态查找的操作,我们可以通过一套计算量较小的方式解决。

    首先对于低left位置0,低left位的值是不确定的,但left自身是已经给出的。

    所以我们可以转为查询B[right] >> left的结果,在拿到结果后加上left的值。

    而对于查找lowBit所在的位置,我们可以用 log ⁡ 2 ( B r & − B r ) \log _2 (B_r \& -B_r) log2(Br&Br) 的方式取得。

    此时,压力来到了对数运算这边。

    具体的更多细节请移步 countTrailingZero

    < O ( n ) , O ( 1 ) > <O(n),O(1)> <O(n)O(1)>


    笛卡尔树


    笛卡尔树是一种特定的二叉树数据结构,可由数列构造,在范围最值查询、范围top k查询(range top k queries)等问题上有广泛应用。
    占位,有时间再写
    部分资料来自 WIKI

    它具有堆的有序性,中序遍历可以输出原数列。

    对于这样一棵树,我们要求它的每个节点由键值对 ( i , v ) (i,v) (iv) 组成,要求 i ( 元 素 下 标 ) i(元素下标) i() 满足二叉搜索树性质、 v ( 元 素 值 ) v(元素值) v() 满足堆性质。

    更进一步讲,给定一个长度为 N N N 序列 A A A,找到其最值 A k A_{k} Ak,将其设为根节点,再将序列拆分成 A ′ = A 1 ∼ A k − 1 A' =A_{1} \sim A_{k-1} A=A1Ak1 A ′ ′ = A k + 1 ∼ A N A'' = A_{k + 1} \sim A_{N} A=Ak+1AN两段,将 A k A_{k} Ak 的左子树设为由 A ′ A' A 迭代此过程的二叉树,将 A k A_{k} Ak 的右子树设为由 A ′ ′ A'' A 迭代此过程的二叉树,如此这般,我们便拿到了由序列 A A A 构成的笛卡尔树。

    由于我们没有改变元素位置,也就是在中序遍历下,元素的下标是还是按原序列递增的,因此 k e y   i key\ i key i 满足二叉搜索树性质,又根节点总是子树(段)的最值,因此 v a l u e   v value\ v value v 满足堆性质。

    根据序列构建一棵笛卡尔树可以在线性时间内完成,我们使用单调栈维护树的堆性质,同时我们需要缓存堆顶弹出的元素来维护树的二叉搜索性质。

    由于画图工程量浩大,
    因此我只能期望读者看到构树部分代码,自行脑补这个过程。

    for (int i = 0; i < N; i++) {
    	k = top;
    	while (k > 0 && A[i] > A[stack[k]]) k--;
    	if (k > 0)
    		right[stack[k]] = i;
    	if (k < top)
    		left[i] = stack[k + 1];
    	stack[++k] = i;
    	top = k;
    }
    

    需要注意的是,使用单调栈构建笛卡尔树,栈内元素的右子树的引用通常是会频繁变动的。

    因此这里推荐使用数组暂存子树引用,而不是直接建边。


    标准 RMQ

    先规约成LCA 再规约成约束RMQ


    对于序列 A A A,我们构建出笛卡尔树 T T T,根据笛卡尔树的堆性质,区间最大值问题就能在线性时间内转为树上最近公共祖先问题。

    详解请移步 Lowest Common Ancestors
    这里不做赘述。

    代码量很大,这里就把完整代码放出来算了。

    import java.io.InputStream;
    import java.io.IOException;
    import java.io.PrintWriter;
    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;
    import java.util.Collection;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Main {
    
        public static void main(String[] args) { new Main().run(); }
    
        public void run() {
            InputReader in = new InputReader(System.in);
            PrintWriter out = new PrintWriter(System.out);
            int N = in.readInt(), M = in.readInt();
            int[] A = new int[N + 1];
            for (int i = 1; i <= N; i++)
                A[i] = in.readInt();
            RMQ r = RMQ.of(A);
            while (M-- > 0)
                out.println(r.query(in.readInt(), in.readInt()));
            out.flush();
        }
    
        public static class RMQ {
    
            private int[] A;
            private LCA lca;
    
            public static RMQ of(int[] A) { return new RMQ(A); }
    
            RMQ(int[] A) {
                List<Edge> edges = new ArrayList();
                int N = A.length;
                int top = 0, k;
                int[] left = new int[N];
                int[] right = new int[N];
                Arrays.fill(left, -1);
                Arrays.fill(right, - 1);
                int[] stack = new int[N + 1];
                for (int i = 0; i < N; i++) {
                    k = top;
                    while (k > 0 && A[i] > A[stack[k]]) k--;
                    if (k > 0)
                        right[stack[k]] = i;
                    if (k < top)
                        left[i] = stack[k + 1];
                    stack[++k] = i;
                    top = k;
                }
                for (int i = 0; i < N; i++) {
                    if (left[i] != -1)
                        edges.add(new Edge(i, left[i]));
                    if (right[i] != -1)
                        edges.add(new Edge(i, right[i]));
                }
                lca = new LCA(N, stack[1], edges);
                this.A = A;
            }
    
            public int query(int i, int j) { return A[lca.query(i, j)]; }
    
            private class Edge {
    
                int v, w;
    
                Edge(int v, int w) {
                    this.v = v;
                    this.w = w;
                }
            }
            
            private class LCA {
    
                private int clock;
                private PlusOrMinusOneRMQ rmq;
                private int[] table, euler, stamp;
                
                LCA(int N, int root, Collection<Edge> edges) {
                    int M = edges.size();
                    table = new int[N + 1];
                    euler = new int[(M + 1 << 1) - 1];
                    stamp = new int[(M + 1 << 1) - 1];
                    List<Integer>[] graph = new List[N + 1];
                    for (int i = 0; i <= N; i++)
                        graph[i] = new ArrayList();
                    for (Edge edge : edges) {
                        graph[edge.v].add(edge.w);
                        graph[edge.w].add(edge.v);
                    }
                    clock = 0;
                    dfs(graph, root, root, 0);
                    rmq = new PlusOrMinusOneRMQ(stamp);
                }
    
                public int query(int i, int j) { return euler[rmq.query(table[i], table[j])]; }
    
                void dfs(List<Integer>[] graph, int v, int fa, int depth) {
                    table[v] = clock;
                    euler[clock] = v;
                    stamp[clock++] = depth;
                    for (int w : graph[v]) {
                        if (w == fa) continue;
                        dfs(graph, w, v, depth + 1);
                        euler[clock] = v;
                        stamp[clock++] = depth;
                    }
                }
    
                private class PlusOrMinusOneRMQ {
    
                    int N, M, K;
                    int[][] ST;
                    int[][][] F;
                    int[] A, block;
    
                    PlusOrMinusOneRMQ(int[] A) { this(A, 0.5); }
    
                    PlusOrMinusOneRMQ(int[] A, double xK) {
                        this.N = A.length;
                        this.K = max(1, (int)(floorLog2(N) * xK));
                        this.M = N / K;
                        if (N % K > 0) M++;
                        block = new int[M];
                        F = new int[1 << K - 1][K][K];
                        ST = new int[M][floorLog2(M) + 1];
                        this.A = A;
                        init();
                    }
    
                    public int query(int i, int j) {
                        if (i > j) return query(j, i);
                        int B1 = i / K, B2 = j / K;
                        int O1 = i % K, O2 = j % K;
                        if (B1 == B2)
                            return B1 * K + F[block[B1]][O1][O2];
                        int LM = F[block[B1]][O1][K - 1] + B1 * K,
                                RM = F[block[B2]][0][O2] + B2 * K;
                        int res = A[LM] < A[RM] ? LM : RM;
                        if (B2 - B1 > 1) {
                            int k = floorLog2(B2 - B1 - 1);
                            int MLM = ST[B1 + 1][k], MRM = ST[B2 - (1 << k)][k];
                            int ans = A[MLM] < A[MRM] ? MLM : MRM;
                            if (A[ans] < A[res]) res = ans;
                        }
                        return res;
                    }
    
                    private void init() {
                        int min, now, block, offset;
                        for (int i = 0; i < M; i++) {
                            min = offset = i * K;
                            block = 0;
                            for (int k = 1; k < K && offset + k < N; k++)
                                if (A[offset + k] < A[offset + k - 1]) {
                                    block |= 1 << k - 1;
                                    if (A[offset + k] < A[min])
                                        min = offset + k;
                                }
                            this.block[i] = block;
                            this.ST[i][0] = min;
                        }
                        for (int k = 1; k <= floorLog2(M); k++)
                            for (int i = 0; i + (1 << k - 1) < M; i++)
                                ST[i][k] = A[ST[i][k - 1]] < A[ST[i + (1 << k - 1)][k - 1]] ? ST[i][k - 1] : ST[i + (1 << k - 1)][k - 1];
                        for (int k = 0, m = 1 << K - 1; k < m; k++)
                            for (int i = 0; i < K; i++) {
                                F[k][i][i] = i;
                                now = 0;
                                min = 0;
                                for (int j = i + 1; j < K; j++) {
                                    F[k][i][j] = F[k][i][j - 1];
                                    if ((k & (1 << j - 1)) == 0) now++;
                                    else if (min > --now) {
                                        F[k][i][j] = j;
                                        min = now;
                                    }
                                }
                            }
                    }
                }
            }
        }
    
        static int[] FLOOR_LOG2_TABLE = { 0, 0, 1, 26, 2, 23, 27, 32, 3, 16, 24, 30, 28, 11, 33, 13, 4, 7, 17, 35, 25, 22, 31, 15, 29, 10, 12, 6, 34, 21, 14, 9, 5, 20, 8, 19, 18 };
    
        public static int floorLog2(int a) { return FLOOR_LOG2_TABLE[highBit(a) % 37]; }
    
        public static int highBit(int a) {
            a |= a >> 1;
            a |= a >> 2;
            a |= a >> 4;
            a |= a >> 8;
            a |= a >> 16;
            return a - (a >>> 1);
        }
    
        public static int max(int a, int b) { return a > b ? a : b; }
    
        public class InputReader {
    
            BufferedReader reader;
            StringTokenizer token;
    
            InputReader(InputStream in) {
                this.reader = new BufferedReader(new InputStreamReader(in));
            }
    
            String read() {
                while (token == null || !token.hasMoreTokens()) {
                    try {
                        token = new StringTokenizer(reader.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                return token.nextToken();
            }
    
            int readInt() { return Integer.parseInt(read()); }
        }
    }
    

    洋洋洒洒二百行

    THE END

    展开全文
  • 文章目录动态规划专题复习(二)最值问题何为最值问题?1.最长回文字串暴力记忆化搜索动态规划2.最小路径暴力记忆化搜索动态规划3.打家劫舍一暴力记忆化搜索动态规划4.打家劫舍二动态规划 动态规划专题复习(二)...

    动态规划专题复习(二)最值问题

    最近在复习算法,为明年的春招做准备,欢迎互关呀,共同学习,进步!

    何为最值问题?

    最值问题就是给出一个问题的最优解,这种最优解,可以是一个问题能求得的最大最小值,一种最优路径等等。

    以下问题均摘取自leetcode

    1.最长回文字串

    在这里插入图片描述

    暴力

    如果使用暴力递归就是遍历所有字串,在遍历字串过程中,判断字串是否是回文串且记录长度

        /**
         * 判断是否是回文串
         * @param str
         * @return
         */
        public boolean isPalindromic(String str){
            int len = str.length();
            for(int i = 0;i < len / 2;i++){
                if(str.charAt(i) != str.charAt(len - i - 1)){
                    return false;
                }
            }
            return true;
        }
    
        /**
         * 暴力解法
         * @param s
         * @return
         */
        public String longestPalindrome(String s) {
            if(s.equals("")){
                return "";
            }
            int len = s.length();
            String result = null;
            int max = 0;
            //遍历所有子串
            for(int i = 0;i < len;i++){
                for(int j = i + 1; j <= len;j++){
                    String str = s.substring(i,j);
                    //判断是否是回文串
                    if(isPalindromic(str) && str.length() > max){
                        result = s.substring(i,j);
                        //是回文串则记录该子串长度
                        max = Math.max(result.length(),max);
                    }
                }
            }
            return result;
        }
    

    记忆化搜索

    使用暴力递归的时间复杂度很高,遍历子串是O(n2),判断是否是回文串则是O(n),则时间复杂度总的就是O(N3),我们要使用记忆化搜索来降低重复的判断

    定义一个记录数组:P(i,j),i是指向从字符串S开始的下标,j是指向从字符串尾部开始的下标

    在这里插入图片描述

    那么

    在这里插入图片描述

    那么,如果我们想知道 P(i,j)是不是回文串,只需要知道Pi+1,j−1)是不是回文串且第i个字符和第j个字符相同即可判断出P(i,j)是回文串

    在这里插入图片描述

        public String longestPailndrome(String s){
            int length = s.length();
            //相当于dp数组,记录中间结果
            boolean[][] P = new boolean[length][length];
            //最大字串
            String maxPal = "";
            //遍历所有的长度
            for (int len = 1; len <= length; len++) { 
                //从字符串起始遍历字串
                for (int start = 0; start < length; start++) {
                    //字串结束下标 = 起始下标 + 字串长度 - 1
                    int end = start + len - 1;
                    //下标已经越界,结束本次循环
                    if (end >= length) { 
                        break;
                    }
                    //P(i,j)=(P(i+1,j−1)&&S[i]==S[j]),长度为 1 和 2 的单独判断下
                    P[start][end] = (len == 1 || len == 2 || P[start + 1][end - 1]) && s.charAt(start) == s.charAt(end); 
                    if (P[start][end]) {
                        //subString(begin,end) ===> 不包括end
                        maxPal = s.substring(start, end + 1);
                    }
                }
            }
            return maxPal;
        }
    

    动态规划

    记忆化搜索是自顶向下的过程,那么,动态规划就是自底向上的过程,是一个逆向过程

        /**
         * 动态规划
         * @param s
         * @return
         */
        public String longestPalindrome1(String s) {
            int length = s.length();
            //最长回文字串
            String result = "";
            //dp数组
            boolean[][] dp = new boolean[length][length];
            //对比记忆化搜索就是逆向遍历的过程
            //i向着字符串开始处遍历,相当于原来的start
            for (int i = length - 1; i >= 0; i--) {
                //j向着字符串尾部遍历,相当于之前的end
                for (int j = i; j < length; j++) {
                    //j - i 代表长度减去 1 ===> 字串长度 = end - start + 1
                    //状态转移方程 ;P(i,j)=(P(i+1,j−1)&&S[i]==S[j])
                    dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
                    if (dp[i][j] &&  j - i + 1 > result.length()) {
                        result = s.substring(i, j + 1);
                    }
                }
            }
            return result;
        }
    

    2.最小路径和

    在这里插入图片描述

    暴力

    递归树如下

    在这里插入图片描述

        /**
         * 暴力解法
         * @param grid
         * @return
         */
        public int minPathSum2(int[][] grid) {
            //从启点开始
            return minpath(grid,0,0);
        }
        
        private int minpath(int[][] grid, int i, int j) {
            if (i == grid.length || j == grid[0].length)
                return Integer.MAX_VALUE;
            //判断是否到达终点
            if(i == grid.length-1 && j == grid[0].length - 1)
                return grid[i][j];
            return grid[i][j] + Math.min(minpath(grid,i + 1,j),minpath(grid,i,j + 1));
        }
    

    记忆化搜索

    从上文的递归树中可以看到有很多重复的计算,利用记忆化搜索暂存这些计算结果

        /**
         * 记忆化搜索
         * @param grid
         * @return
         */
        public int minPathSum(int[][] grid) {
            int[][] dp = new int[grid.length+1][grid[0].length+1];
            //从启点开始
            return minpath1(grid,0,0,dp);
        }
    
        private int minpath1(int[][] grid, int i, int j,int[][] dp) {
            if (i == grid.length || j == grid[0].length)
                return Integer.MAX_VALUE;
            //判断是否到达终点
            if(i == grid.length-1 && j == grid[0].length - 1)
                return grid[i][j];
            if(dp[i][j] != 0){
                return dp[i][j];
            }
            //暂存计算结果
            dp[i][j] = grid[i][j] + Math.min(minpath1(grid,i + 1,j,dp),minpath1(grid,i,j + 1,dp));
            return dp[i][j];
        }
    

    动态规划

    那么动态规划就是一个自底向上的过程

    在这里插入图片描述

        public int minPathSum1(int[][] grid) {
            for(int i = 0;i<grid.length;i++){
                for(int j = 0;j<grid[0].length;j++){
                    //第一列
                    if(i == 0 && j != 0) grid[i][j] += grid[i][j - 1];
                    //第一行
                    if(i != 0 && j == 0) grid[i][j] += grid[i - 1][j];
                    //dp动态转移方程:grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
                    if(i != 0 && j != 0) grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]);
                }
            }
            return grid[grid.length-1][grid[0].length - 1];
        }
    

    3.打家劫舍一

    在这里插入图片描述

    暴力

        /**
         * 暴力递归
         * @param nums
         * @return
         */
        public int rob1(int[] nums){
            return tryRob(0,nums);
        }
        
        public int tryRob(int index,int[] nums){
            if(index >= nums.length){
                return 0;
            }
            int max = 0;
            for(int i = index;i < nums.length;i++){
                //max:之前能偷取到的最大金额
                //tryRob(i + 2)继续偷取下下家房子,然后算出偷上下下家房子后的总金额
                max = Math.max(max,nums[i] + tryRob(i + 2,nums));
            }
            return max;
        }
    

    记忆化搜索

        /**
         * 记忆化搜索
         * @param nums
         * @return
         */
        public int rob2(int[] nums){
            int[] dp = new int[nums.length];
            return tryRob1(0,nums,dp);
        }
    
        public int tryRob1(int index,int[] nums,int[] dp){
            if(index >= nums.length){
                return 0;
            }
            if(dp[index] != 0){
                return dp[index];
            }
            int max = 0;
            for(int i = index;i < nums.length;i++){
                max = Math.max(max,nums[i] + tryRob1(i + 2,nums,dp));
            }
            dp[index] = max;
            return max;
        }
    

    动态规划

    由于不可以在相邻的房屋闯入,所以在当前位置 n 房屋可盗窃的最大值,要么就是 n-1 房屋可盗窃的最大值,要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值,二者之间取最大值,dp[i] 代表前 i 个房子在满足条件下的能偷窃到的最高金额。

    在这里插入图片描述

        public int rob(int[] nums) {
            if(nums.length == 0){
                return 0;
            }
            int[] dp =new int[nums.length + 1];
            dp[0] = 0;
            dp[1] = nums[0];
            for(int i = 2;i <= nums.length;i++){
                //状态转移方程:dp[i] = max{dp[i-1],dp[i-2]+nums[i-1]}
                dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
            }
            return dp[nums.length];
        }
    

    4.打家劫舍二

    在这里插入图片描述

    这道题目和第一道打家劫舍的区别就是这道题房屋是环状的,第一道是线性排列,也就是说在这里,头尾的房子是相邻的,只能二选一,因此,我们可以将这个题目分解为两个第一类的打家劫舍

    • 在不偷窃第一个房子的情况下最大金额是 p1;
    • 在不偷窃最后一个房子的情况下最大金额是 p2 。
    • 取p1,p2最大值

    动态规划

        public int rob(int[] nums) {
            if(nums.length == 0) return 0;
            if(nums.length == 1) return nums[0];
            return Math.max(tryRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                    tryRob(Arrays.copyOfRange(nums, 1, nums.length)));
        }
    
    
        public int tryRob(int[] nums) {
            if(nums.length == 0){
                return 0;
            }
            int[] dp =new int[nums.length + 1];
            dp[0] = 0;
            dp[1] = nums[0];
            for(int i = 2;i <= nums.length;i++){
                //状态转移方程:dp[i] = max{dp[i-1],dp[i-2]+nums[i-1]}
                dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
            }
            return dp[nums.length];
        }
    

    5.最大子序和

    在这里插入图片描述

    暴力

        /**
         * 暴力穷举
         * @param nums
         * @return
         */
        public int maxSubArray1(int[] nums) {
            int sum;
            int max = Integer.MIN_VALUE;
            //穷举所有子序
            for(int i = 0;i < nums.length;i++){
                sum = 0;
                for(int j = i ;j < nums.length;j++){
                    sum += nums[j];
                    if(sum > max){
                        max = sum;
                    }
                }
            }
            return max;
        }
    

    动态规划

    状态转移方程:sum(i) = Max{sum(i - 1) + nums[i] ,nums[i]}

    sum(i) —> 代表从0开始的到i的闭区间中,所有连续子数组的和的最大值

        /**
         * 动态规划
         * @param nums
         * @return
         */
        public int maxSubArray2(int[] nums) {
           int[] dp = new int[nums.length];
           dp[0] = nums[0];
           //记录子数组最大和 
           int max = dp[0];
           for(int i = 1;i < nums.length;i++){
               //状态转移方程:sum(i) = Max{sum(i - 1) + nums[i] ,nums[i]}
               dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
               if(dp[i] > max){
                   max = dp[i];
               }
           }
           return max;
        }
    

    6.最大子序积

    在这里插入图片描述

    动态规划

    最大乘积可以由正数正数和负数负数得到,因此,需要同时记录下最大值和最小值。

    在这里插入图片描述

        public int maxProduct(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            //记录结果
            int result = nums[0];
            int dpMax = nums[0];
            int dpMin = nums[0];
            for (int i = 1; i < nums.length; i++) {
                int curMax = Math.max(Math.max(dpMax * nums[i], dpMin * nums[i]), nums[i]);
                int curMin = Math.min(Math.min(dpMax * nums[i], dpMin * nums[i]), nums[i]);
                result = Math.max(result, curMax);
                dpMax = curMax;
                dpMin = curMin;
            }
            return result;
        }
    

    7.最佳买卖股票时机

    在这里插入图片描述

    暴力

        public int maxProfit(int[] prices) {
            int max = 0;
            //从第一个元素遍历到倒数第二个元素
            for(int i = 0;i < prices.length-1;i++){
                //从第二个元素遍历到最后一个元素,保证买入在卖出前
                for(int j = i+1;j < prices.length;j++){
                    int profile = prices[j] - prices[i];
                    if(profile > max){
                        max = profile;
                    }
                }
            }
            return max;
        }
    

    动态规划

        public int maxProfitWithDp1(int[] prices) {
            if(prices.length == 0){
                return 0;
            }
            //最小买入价
            int min = prices[0];
            //最大利润
            int max = 0;
            for(int i = 0;i<prices.length;i++){
                //找出最小买入价
                min = Math.min(prices[i],min);
                //找到最大利润
                max = Math.max(max,prices[i] - min);
            }
            return max;
        }
    

    其实这道题目虽然在leetcode上归类为动态规划,但是我并不觉得这道题目在动态规划思想上有很多的体现

    8.最佳买卖股票时机含冷冻期

    在这里插入图片描述

    状态分析

    主要有三种状态:

    • 持有股票
    • 卖出股票
    • 冷冻期(什么都不干)

    由于存在三种状态,所以时间复杂度可以达到O(3^n)

    状态转换图:

    在这里插入图片描述

    推导状态转移方程:

    在这里插入图片描述

    动态规划

        public int maxProfit(int[] prices) {
            int sold = 0;
            int rest = 0;
            int hold = Integer.MIN_VALUE;
            for(int i : prices){
                int preSold = sold;
                //状态转移方程:
                    // newHold = Max{oldHold,rest - price[i]}
                    // newSold = hold + price[i]
                    // newRest = Max{oldRest,oldSold}
                sold = hold + i;
                hold = Math.max(hold,rest - i);
                rest = Math.max(preSold,rest);
            }
            return Math.max(sold,rest);
        }
    

    9.买卖股票的最佳时机 II尽可能多的交易

    在这里插入图片描述

    暴力

        public int maxProfit(int[] prices) {
            return getMaxProfit(prices,0);
        }
    
        /**
         * 暴力
         * @param prices
         * @param start
         * @return
         */
        public int getMaxProfit(int prices[], int start){
            //边界条件
            if(start >= prices.length){
                return 0;
            }
            //最大利润
            int max = 0;
            for(int i = start;i < prices.length;i++){
                int maxProfit = 0;
                for(int j = i + 1;j < prices.length;j++){
                    if(prices[i] < prices[j]){
                        //尽可能多的交易,在j卖出后,马上在j(即i + 1)买入,然后就继续寻找下一个卖出点
                        int profit = prices[j] - prices[i] + getMaxProfit(prices,i+1);
                        if(maxProfit < profit){
                            maxProfit = profit;
                        }
                    }
                }
                if(max < maxProfit){
                    max = maxProfit;
                }
            }
            return max;
        }
    

    同一天可以先卖出,再买入(等于这天没有操作),比如 [1, 2, 3],我们可以第一天买入,第二天卖出得 2 - 1, 第二天再买入,第三天卖出得3 - 2,总共2,相当于第二天不用操作也行.受上一题思路,如果存在数组为[a1, a2, a3] ,那么 a3 - a1 = (a2 - a1) + (a3 - a2),所以只看今明两天,只要明天比今天贵,那今天买明天卖就赚到,否则不做操作就是相当于+0,以此类推即可。

        /**
         * 贪心算法
         * @param prices
         * @return
         */
        public int maxProfit1(int[] prices) {
            int result = 0;
            for(int i = 1;i < prices.length;i++){
                result += Math.max(0,prices[i] - prices[i - 1]);
            }
            return result;
        }
    

    动态规划

    对于这道题目,我认为python写起来更易懂

    状态图:

    在这里插入图片描述

        def maxProfit(self, prices: List[int]) -> int:
            if not prices:
                return 0
            n = len(prices)
            dp = [[0]*2 for _ in range(n)]
            # dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票
            dp[0][0], dp[0][1] = 0, - prices[0]
            for i in range(1, n):
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
                dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
            return dp[n-1][0]
    
    展开全文
  • 88. 最值问题 时间限制1000 ms内存限制65536 KB 题目描述 给出N个数,求出这N个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试数据的...
  • 熟悉初中教材,能准确把握教学重点难点,教学风格细致最值问题之费马点模型人类每天为解决最大最小问题而忙碌着,大自然亦是如此。最早指出自然界中到处都潜藏着最大最小问题的人,大概是费马。Q:Who is 费马?费马...
  • 最值问题大归纳

    千次阅读 2018-10-30 13:52:02
    最值问题一直是高考的一个热门考点,因其综合性强、思维难度可以出的很高而受到命题人的青睐。最值问题综合了高中的数列、不等式、函数、解析几何等的知识,可以说几乎是高中数学的半壁江山了(求取值范围也可以看成...
  • 最值问题-北邮OJ88

    2019-02-26 08:23:34
    88. 最值问题 时间限制 1000 ms 内存限制 65536 KB 题目描述 给出N个数,求出这N个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试...
  • 二叉树中的最值问题

    2021-12-06 20:30:43
    543. 二叉树的直径 - E 687. 最长同值路径 - M 124. 二叉树中的最大路径 这三道题使用同一种套路:递归 1. 二叉树直径 二叉树的直径:
  • 121.最值问题

    2019-03-17 00:28:43
    输入保证个数中至少存在两个不同的数。 输入格式 第一行为测试数据的组数。请注意,任意两组测试数据之间是相互独立的。 每组数据包括两行: 第一行为一个整数。 第二行为个正整数,每个整数均不大于。 输出格式 ...
  • 求数组中的最值问题

    千次阅读 2019-03-13 23:12:09
    遇到求数组最值得问题,我们一般有两种解决方式,大多数情况下,我们运用的都是从数组元素入手,却忽略了数组角标的存在和意义,接下来,我们来看看,数组中求解最值问题的两种解决方法: 方法一、从数组元素入手...
  • 本文介绍了利用导数判断函数单调性、凹凸性、极值相关的概念定理,通过本文的介绍,可以熟悉通过导数判断函数单调性、凹凸性、极值以及求最值的原理方法。最后,通过一阶导数二阶导数确定了函数的单调性、凹凸...
  • 最值问题

    2019-09-27 14:32:49
    描述:给出N个数,求出这N个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。 输入:第一行为测试数据的组数T(T≤20)。请注意,任意两组测试数据之间是相互独立的...
  • 新BOJ 88. 最值问题

    2016-03-11 08:19:59
    88. 最值问题 时间限制 1000 ms 内存限制 65536 KB  题目描述 给出N 个数,求出这N 个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N 个数中至少存在两个不同的数。 输入格式 第...
  • 文章目录 引入倍增: 例题1:区间 例题2:Genius ACM 应用: ST算法 求解 RMQ(区间最值问题) 模板Code: 练习题: ST算法 维护区间最大公约数 例题:Pair of Numbers 引入倍增: 所谓倍增,就是成倍增长。...
  • BOJ 88 最值问题

    2019-09-23 13:47:42
    给出N个数,求出这N个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试数据的组数T(T≤20)。请注意,任意两组测试数据之间是相互独立...
  • 给你\(m\)个序列,每个序列有\(n\)个非负整数,你现在要在每个序列选一个数,这一共有\(n^m\)种方案,一种方案的值定义为所选的数的,要你输出值最小的\(n\)种方案的。 数据范围: \(0 \lt m \le 100\), \(0 \lt...
  • 88. 最值问题 时间限制 1000 ms 内存限制 65536 KB 题目描述 给出N个数,求出这N个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试数据的组...
  • 给出N个数,求出这N个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试数据的组数T(T≤20)。请注意,任意两组测试数据之间是相互独立的。 ...
  • bupt|121. 最值问题

    2020-04-16 21:06:47
    给出N个数,求出这N个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试数据的组数T(T≤20)。请注意,任意两组测试数据之间是相互独立的。 每...
  • 某些平面几何问题,由于图形中的几何性质比较隐晦,条件分散,题设与结论间的某些元素的相互关系在所给的图形中不易发现,使之难以思考而感到束手无策.如果我们能对图形作各种恰当的变换,把原图形或原图形中的一...
  • 思路:(来自大佬) 先对式子进行简化,可以变成求区间所有最大值之减去区间所有最小值之。那么关键就在于求出所有区间的最大值以及最小值。但是如果光暴力的话(枚举区间长度+区间平移),是会超时的,那么...
  • 输入保证N个数中至少存在两个不同的数。 输入描述 第一行为测试数据的组数T(T≤20)。请注意,任意两组测试数据之间是相互独立的。 每组数据包括两行: 第一行为一个整数N(1≤N≤1000)。 第二行为N个正整数,每个整数...
  • 88. 最值问题 时间限制1000 ms内存限制65536 KB 题目描述 给出N个数,求出这N个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试数据的...
  • 正定矩阵相关应用-最值问题

    千次阅读 2019-01-06 00:21:45
    最值问题始终是一个值得研究的问题,确定解的问题不是那么多,最优解更具有普适性。 最小原理 最小原理在物理现象中很常见。重液体一沉到底就是使其势能最小化的结果。这些势能的表达式,正是二次型。研究二次型的...
  • 输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试数据的组数T(T≤20)。请注意,任意两组测试数据之间是相互独立的。 每组数据包括两行: 第一行为一个整数N(1≤N≤1000)。 第二行为N个正整数,每...
  • 输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试数据的组数T(T≤20)。请注意,任意两组测试数据之间是相互独立的。 每组数据包括两行: 第一行为一个整数N(1≤N≤1000)。 第二行为N个正整数,每个整数...
  • 最值问题 时间限制 1000 ms 内存限制 65536 KB 题目描述 给出N个数,求出这N个数中最大值次大值。注意这里的次大值必须严格小于最大值。输入保证N个数中至少存在两个不同的数。 输入格式 第一行为测试数据的...
  • 约束最值问题的拉格朗日对偶性

    千次阅读 2017-06-06 21:20:34
    约束最优化,拉格朗日对偶问题
  • HarelTarjan是首先仔细研究该问题的人,他们想出了一种在输入一棵树后,通过线性时间的预处理,便可以在常数时间内求解LCA的询问的办法。他们的工作早就被拓展了,这篇教程将会带来一些同样能够应用在另外一些问题...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,406
精华内容 2,162
关键字:

存在和任意的最值问题