精华内容
下载资源
问答
  • 最长单调子序列

    2021-03-05 22:52:06
    最近在opj上刷动态规划,遇到的比较多的就是最长单调子序列问题,有几道题调着确实挺费劲,写一下。 描述 一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2...

    最近在opj上刷动态规划,遇到的比较多的就是最长单调子序列问题,有几道题调着确实挺费劲,写一下。
    描述
    一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8).

    你的任务,就是对于给定的序列,求出最长上升子序列的长度。
    输入
    输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。
    输出
    最长上升子序列的长度。
    这道题是最长上升子序列的模版题,基本思路就是维护一个队列,如果新的元素等于队尾,直接跳过,如果大于队尾就加长队伍,存入新元素,如果小于就在队列里搜第一个大于它的元素并将其替换掉。搜的方法可以是从前到后扫也可以是二分,视数据范围而定。
    以下是可以视作模版代码的代码

    #include<cstdio>
    using namespace std;
    int n;
    int a[100001] = { };
    int ans[100001] = { };
    int main(){
        scanf("%d" ,&n);
        for(int i = 1;i <= n; i++){
            scanf("%d" ,&a[i]);
        }
        ans[1] = a[1];
        int k = 1;
        for(int i = 2;i <= n; i++){
            if(ans[k] < a[i]){
                k++;
                ans[k] = a[i];
            }
            if(ans[k] == a[i]) continue;
            if(ans[k] > a[i]){
                for(int j = 1;j <= k; j++){//个人水平比较low,直接从前到后扫一遍了
                    if(ans[j] > a[i]){
                        ans[j] = a[i];
                        break;
                    }
                }
            }
        }
        printf("%d" ,k);
        return 0;
    }
    

    接下来是它的一种变式(其他的变式由于个人太菜,题量不够还没有全部整理好,会慢慢更)
    描述
    怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
    有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪装,而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已,怪盗基德只能操作受损的滑翔翼逃脱。
    假设城市中一共有N幢建筑排成一条线,每幢建筑的高度各不相同。初始时,怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑,但是不能中途改变方向(因为中森警部会在后面追击)。因为滑翔翼动力装置受损,他只能往下滑行(即:只能从较高的建筑滑翔到较低的建筑)。他希望尽可能多地经过不同建筑的顶部,这样可以减缓下降时的冲击力,减少受伤的可能性。请问,他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)?
    输入
    输入数据第一行是一个整数K(K < 100),代表有K组测试数据。
    每组测试数据包含两行:第一行是一个整数N(N < 100),代表有N幢建筑。第二行包含N个不同的整数,每一个对应一幢建筑的高度h(0 < h < 10000),按照建筑的排列顺序给出。
    输出
    对于每一组测试数据,输出一行,包含一个整数,代表怪盗基德最多可以经过的建筑数量。
    这道题我们可以发现,首先是一个最长不上升子序列,那么我们刚刚求出了最长不下降子序列,所以我们只需要把循环反过来,从后往前扫就可以了,但是这道题还有一个神奇的条件,就是他可以选择任意的方向,这就可以正着扫一遍,反着扫一遍,取最大值输出

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,k;
    int a[10001] = { };
    int dp_f[10001] = { };
    int dp_b[10001] = { };
    int main()
    {
        scanf("%d" ,&k);
        for(int l = 1;l <= k; l++){
            memset(a,0,sizeof(a));
            memset(dp_f,0,sizeof(dp_f));
            memset(dp_b,0,sizeof(dp_b));
            scanf("%d" ,&n);
            for(int i = 1;i <= n; i++){
                scanf("%d" ,&a[i]);
            }
            dp_b[1] = a[n];
            int ans_b = 1;
            for(int i = n;i >= 1; i--){
                if(a[i] == dp_b[ans_b]) continue;
                if(a[i] > dp_b[ans_b]){
                    ans_b++;
                    dp_b[ans_b] = a[i];
                }
                if(a[i] < dp_b[ans_b]){
                    for(int j = 1;j <= ans_b; j++){
                        if(dp_b[j] > a[i]){
                            dp_b[j] = a[i];
                            break;
                        }
                    }
                }
            }
            dp_f[1] = a[1];
            int ans_f = 1;
            for(int i = 1;i <= n; i++){
                if(a[i] == dp_f[ans_f]) continue;
                if(a[i] > dp_f[ans_f]){
                    ans_f++;
                    dp_f[ans_f] = a[i];
                }
                if(a[i] < dp_f[ans_f]){
                    for(int j = 1;j <= ans_f; j++){
                        if(dp_f[j] > a[i]){
                            dp_f[j] = a[i];
                            break;
                        }
                    }
                }
            }
            printf("%d\n" ,max(ans_b,ans_f));
        }
        return 0;
    }
    

    由于本人水平太过垃圾,有的题型还没有整理到,日后会慢慢更QAQ

    展开全文
  • 文章目录 一、前言 二、最长单调子序列的定义 1、单调序列 2、单调子序列 3、最长单调子序列 三、最长单调子序列的求解 1、暴力解法 2、朴素解法 1)设计状态 2)状态转移方程 3)时间复杂度分析 四、最长单调子序列...

    一、前言

      对于成功者来说,仅仅拥有目标是远远不够的,就算你将一切准备就绪,无论是在知识与技巧、态度和能力方面都做到无可挑剔,可是一直没有采取实际的行动,那么一切美好的愿望都只是海市蜃楼,遥不可及。
      现如今经济飞速发展,我们要知道 “不进则退,慢进也是退” 的道理,只有当你采取快速高效的行动之后,才能够在残酷的竞争中拥有自己的一席之地!

    二、最长单调子序列的定义

    1、单调序列

    • 单调序列就是一个满足某种单调性的数组序列,比如 单调递增序列、单调递减序列、单调不增序列、单调不减序列。

    举几个简单的例子:
      单调递增序列:1,2,3,7,9
      单调递减序列:9,8,4,2,1
      单调不增序列:9,8,8,5,2
      单调不减序列:1,2,2,5,5

    • 一个比较直观的单调递增序列的例子就是一个楼梯的侧面。
      图二-1-1
    • 我们可以把这个楼梯每一阶的高度用一个数字表示,得到一个单调递增序列,如图二-1-2所示:
      图二-1-2
    • 进阶:事实上,这几个例子只是数值上的单调,更加宽泛的,我们在编码过程中,只要重载struct的 ‘<’ 运算符,或者实现 less 仿函数,就能对任意struct或者class进行小于比较,实现结构体或者类的单调。在离散数学中,这种关系被称为 “偏序” 关系,有兴趣的读者可以翻查相关资料进行进一步了解。

    2、单调子序列

    • 单调子序列指的是任意一个数组序列,按顺序选择一些元素组成一个新的序列,并且满足单调性。对于一个长度为 nn 的序列,每个元素可以选择 “取” 或者 “不取”,所以最多情况下,有 2n2^n 个单调子序列。
    • 如图二-2-1所示,代表的是序列:[1,2,4,6,3,5,9]
      图二-2-1
    • 其中 [1,2,6] 为它的一个长度为 3 的单调子序列,如图二-2-2所示;
      图二-2-2
    • [1,3,6] 则不是,因为 3 和 6 的顺序不是原序列中的顺序;[1,4,3] 也不是,因为它不满足单调性。

    3、最长单调子序列

    • 最长单调子序列是指对于原数组序列,能够找到的元素个数最多的单调子序列。
    • 还是以 [1,2,4,6,3,5,9] 为例,它的最长单调子序列为:[1,2,4,6,9],长度为 5;
      图二-3-1
    • 当然,也可以是 [1,2,3,5,9],长度同样为 5。在这里插入图片描述
      图二-3-2

    三、最长单调子序列的求解

    【例题1】给定一个长度为 n(1n1000)n(1 \le n \le 1000) 的数组 aia_i,求给出它的最长递增子序列的长度。

    1、暴力解法

    • 所谓暴力解法,就是穷举所有情况。因为对于长度为 nn 的原序列,它的子序列总共有 2n2^n 种情况,所以利用深度优先搜索枚举所有情况,然后取 “满足相邻两元素递增并且长度最长” 的子序列就是答案,当然这种方法肯定是不可取的,因为随着 nn 的不断变大,整个求解时间复杂度呈指数级增长。

    2、朴素解法

    • 朴素解法采用的是动态规划的思想。首先当然是设计状态。

    1)设计状态

    • 对于数组序列 ai(1in)a_i(1 \le i \le n),令 f[i]f[i] 表示以第 ii 个数 aia_i 结尾的最长递增子序列的长度。
    • 那么,我们考虑以第 ii 个数 aia_i 结尾的最长递增子序列,它在这个序列中的前一个数一定是 aj(1j<i)a_j(1 \le j < i) 中的一个,所以,如果我们已经知道了 f[j]f[j],那么就有 f[i]=f[j]+1f[i] = f[j] + 1。显然,我们还需要满足 aj<aia_j < a_i 这个递增的限制条件。

    2)状态转移方程

    • 那么就可以得出状态转移方程:f[i]=maxj=1i1(f[j]  aj<ai)+1f[i] = \max_{j=1}^{i-1} (f[j] \ | \ a_j < a_i) + 1
    • 这里 f[j]f[j]f[i]f[i] 的子结构,而 max(f[j])max(f[j])f[i]f[i] 的最优子结构,当然我们需要考虑一种情况,就是没有找到最优子结构的时候,例如:i=1i=1 或者 不存在 aj<aia_j < a_ijj,此时 f[i]=1f[i] = 1,表示 aia_i 本身是一个长度为 11 的最长递增子序列。
    • f[i]f[i] 数组可以通过两层循环来求解,如下图表所示:

    3)时间复杂度分析

    • 状态数 f[...]f[...] 总共 O(n)O(n) 个,状态转移的消耗为 O(n)O(n),所以总的时间复杂度为 O(n2)O(n^2),所以对于这类问题,一般能够接受的 nn 的范围在千级别,也就是 1000,2000,3000...1000, 2000, 3000 ...。如果是 n=10000,100000n=10000, 100000 的情况,就需要考虑优化了。
    • 那么,下文将介绍最长单调子序列的优化算法,基于的是 贪心 的思想,为了方便理解,将 “单调” 一词替换为 “递增”。均以 最长递增子序列 为例进行讲解。

    四、最长单调子序列的优化

    【例题2】给定一个长度为 n(1n105)n(1 \le n \le 10^5) 的数组 aia_i,求它的最长递增子序列的长度。

    • 【例题2】和 【例题1】 的区别就在于,数据量扩大了 100 倍,对于原先 O(n2)O(n^2) 的算法,在这里不再适用。
    • 我们还是以第 ii 个元素 aia_i 作为问题的切入口,思考这么一个问题:
    • 假设前面 i1i-1 个元素组成的长度为 1 的,长度为 2 的,长度为 3 的,… 长度为 i1i-1 的递增子序列都已经知道了,我们如何用 aia_i 去更新得到 长度为 1 的,长度为 2 的,长度为 3 的,… 长度为 ii 的递增子序列。
    • 如下图表展示的情况,长度为 1 到 4 的递增子序列分别如下:
    • 当下一个数为 3 的时候,上述递增子序列会有什么样的变化?
    • 我们可以将长度为 3 的序列最后一个元素从 4 替换为 3,考虑后面如果再出现 4 的情况,[1 2 3] 可以变成 [1 2 3 4],长度加 1,而 [1 2 4] 不行,所以 [1 2 3] 一定比 [1 2 4] 更优。
    • 基于这一步贪心的思想,我们可以设计如下状态。

    1)设计状态

    • g[i]g[i] 表示长度为 ii 的 递增子序列的最后一个数(即子序列中的第 ii 个数)的最小值。

    2)状态转移

    • 怎么理解这个状态呢?我们可以这么考虑,对于前面 kk 个数,有长度分别为 123...k1,2,3,...,k 的递增子序列。
    • 以长度为 i(1ik)i(1 \le i \le k) 的递增子序列为例,我们只需要记录下它的最后一个数(因为前面的数一定比最后一个数小),而且在长度限定为 ii 的情况下,最后一个数一定是越小越好(更加利于后续的状态转移,参考上述的贪心思想)。
    • 举个例子,对于原序列:[30,40,10,30,60,40,50]

    g[...]g[...] 数组的生成过程如下:
      1)初始化 g[...]=[]g[...] = []
      2)枚举所有的 ak(1kn)a_k (1 \le k \le n),然后去现有的 g[...]g[...] 数组中找到一个满足 akg[j]a_k \le g[j] 且最小的 jj
        2.a)如果找到了,则用 aka_k 替换 g[j]g[j],即 g[j]=akg[j] = a_k
        2.b)否则,在 g[...]g[...] 尾部插入 aka_k

    • 以枚举到第 3 个数的时候为例,原先长度为 1 的递增子序列的最后一个值的最小值为 30,当出现 a3=10a_3 = 10 时,长度为 1 的递增子序列的最后一个数用 a3a_3 来代替肯定更优,所以 g[1]=a3g[1] = a_3
    • 再来看枚举到第 6 个数的时候,原先长度为 3 的递增子序列的最后一个值的最小值为 60,当出现 a6=40a_6 = 40 时,长度为 3 的递增子序列的最后一个数用 a6a_6 来代替肯定更优,所以 g[3]=a6g[3] = a_6
    • 最后 g[...]g[...] 数组的长度就是原序列最长递增子序列的值。
    • 需要注意的是:为了更加便于理解,这里假设 g[...]g[...] 数组的下标是从 11 开始的,也就是 g[0]g[0] 是无意义的,因为长度为 0 的递增子序列本身也不存在最后一个数。

    3)时间复杂度分析

    • 状态数 g[...]g[...] 总共 O(n)O(n) 个,状态转移的消耗为 O(n)O(n),所以总的时间复杂度为 O(n2)O(n^2),但是我们可以发现,这里的 g[...]g[...] 数组是一个单调递增的数组,所以是有优化余地的。

    4)二分查找优化

    • 上文给出的算法中,基于 g[...]g[...] 本身的单调性,从 " 现有的 g[...]g[...] 数组中找到一个满足 akg[j]a_k \le g[j] 且最小的 jj " 这一步,是可以通过二分查找来完成的,所以这一步查找的时间复杂度为 O(log2n)O(log_2n) ,找到后的替换(插入)aka_k 操作是 O(1)O(1) 的,所以整个状态转移的过程是 O(log2n)O(log_2n) 的。算法时间复杂度优化到 O(nlog2n)O(nlog_2n)

    5)代码实现

    1. 贪心部分

    enum LISType {
        LIST_STRICTLY = 0,            // 严格单调
        LIST_NOTSTRICTLY = 1,         // 非严格单调
    };
    void findLIS(LISType lt, ValueType *a, int asize, ValueType *g, int& gsize) {
        gsize = 0;
        for (int i = 1; i <= asize; ++i) {
            int pos = findLISIndex(lt, a[i], g, gsize);
            if (pos == -1) {
                pos = ++gsize;
            }
            g[pos] = a[i];
        }
    }
    
    • 1)参数介绍:LISType 代表我们要求解的问题是严格单调的,还是非严格单调的。这里统一介绍递增类问题,至于递减类的问题,可以通过将数组逆序后转化为递增类问题来解决。数组 aa 为原数组,asizeasize 为它的元素个数,gg 为上文提到的状态数组,gsizegsizegg 数组的大小。
    • 2)贪心部分就是线性扫描一遍原数组 aa,在 gg 数组中找到一个最合适放置 aia_i 的位置 pospos,并且替换原有 g[pos]g[pos] 的值,当找不到这个位置时,就将 aia_i 插入到 gg 数组尾部,对应上文 pospos 返回 -1 的情况。
    • 而找 pospos 这个位置的方式是通过二分部分来实现的,也就是 findLISIndex函数。

    2. 二分部分

    int findLISIndex(LISType lt, ValueType val, ValueType *g, int& gsize) {
        int l = 1, r = gsize, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (cmpLIS(lt, val, g[mid])) {
                ans = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        return ans;
    }
    
    • 这里我们需要求两种情况:单调递增 和 单调不降。所以将比较函数抽成了cmpLIS,比较函数实现如下:
    bool cmpLIS(LISType lt, ValueType a, ValueType b) {
        if (LIST_STRICTLY == lt) {
            return a <= b;
        }
        else if (LIST_NOTSTRICTLY == lt) {
            return a < b;
        }
    }
    
    • 如果要求严格单调递增,那么需要满足 a[i] <= g[mid];如果要求非严格单调递增,也就是单调不降,只需要满足 a[i] < g[mid];这一点,交给读者自己思考。提醒一下,可以从 gg 数组的定义出发来思考。

    五、最长单调子序列的应用

    1、单调子序列的最少划分

    【例题3】有种导弹拦截系统,它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度,给出导弹依此飞来的高度,请帮助计算一下最少需要多少套拦截系统。

    • 我们把问题简化如下:给定一个序列,将它拆分成单调不增的子序列,并且要求拆分数最少,求最少的次数。
    • 这里引入一个定理,然后简单加以证明。
    • Dilworth定理:对于任意一个序列,它的 单调不增子序列最少划分数 等于 最长递增子序列的长度
    • 例如对于原序列:[1, 5, 7, 4, 5, 6, 6],现在需要把它划分成 kk 个序列,并且保证每个序列都单调不增,那么 kk 至少为 4。可以分成如下 4 个序列:[1]、[5, 4]、[7, 5]、[6, 6],不能再少了,而这正好是原序列最长递增子序列的长度。
    • 证明:证明过程采用反证法,如下:
    • 1)首先,令原序列的最长递增子序列的长度为 ll
    • 2)并且,我们假设可以将原序列划分成 kk 个序列,并且每个序列中的元素都是单调不增的;
    • 3)然后,假设 l>kl > k,根据鸽巢原理,每个序列最多可以放一个 “最长递增子序列” 上的元素,所以剩下的 lkl-k 个元素势必又要开辟单独的 lkl-k 个单调不增的序列,和 2)的假设矛盾,所以容易得到 lkl \le k
    • 4)最后,我们要求的是划分的最小值,也就是 kk 的最小值,基于 3) 的证明,这个最小值就是 ll

    【例题4】一个 n×m(1n,m24)n \times m (1 \le n,m \le 24) 的格子图上,有一些坑,现在需要派出一些机器人来填充这些坑,机器人只能往下或者往右走,走到右下角就不能回头了。

    • 这个问题同样可以利用 Dilworth定理 求解。
    • 可以这样考虑,将每个 EE 点按照第一关键字 xx 、第二关键字 yy 进行递增排序;假设有两个点 a(ax,ay)a(a_x, a_y)b(bx,by)b(b_x, b_y)aa 排在 bb 的前面,那么只要 ay<bya_y < b_y,它们一定可以用一个机器人搞定,于是就组成一个偏序关系。那么我们现在要求原序列的单调递增子序列的最少划分数,利用 Dilworth定理 进行转换后,其实就是求最长单调不增子序列的长度,这里的比较关键字是 yy
    • 最长单调不增子序列可以转换成逆序的最长单调不降子序列来求。

    2、最长单调子序列的字典序最小解

    【例题5】给定数组 aa,设长度为 nn,输出 aa 的最长递增子序列(如果有多个答案,请输出其中字典序最小的)。
    对于序列 [1,2,8,6,4],其最长递增子序列有3个,[1,2,8], [1,2,6], [1,2,4],其中第三个字典序最小,故答案为 [1, 2, 4]。

    • 首先,如果没有字典序最小这个要求,我们怎么来求它的一个解。
    • 回忆一下,对于最长递增子序列,我们在计算 gg 数组的时候,是通过二分查找从 " 现有的 g[...]g[...] 数组中找到一个满足 akg[j]a_k \le g[j] 且最小的 jj ",并且替换 g[j]=akg[j] = a_k,那么很显然,这个时候,以 aka_k 结尾的最长递增子序列的前驱一定是 g[j1]g[j-1]
    • 所以可以用一个前驱数组 pp 记录以每个数结尾的最长递增子序列的前驱,即 p[k]=index_of(g[j1])p[k] = index\_of( g[j-1] )index_ofindex\_of 的含义是什么呢?我们记录前驱的目的,是因为需要利用前驱来回溯路径,那么一定要记录下标,而不是值,所以 index_ofindex\_of 是通过值来反查下标的。
    • 反查下标这一步肯定是 O(n)O(n) 的,而且对于有重复元素的情况会导致算法错误,所以我们可以在更新 gg 数组的同时,更新下标在 idxidx 数组中;
    • 调整后的算法如下:
    void findLIS(LISType lt, ValueType *a, int asize) {
        gsize = 0;
        idx[0] = -1;
        for (int i = 1; i <= asize; ++i) {
            int ans = findLISIndex(lt, a[i], g, gsize);
            if (ans == -1) {
                ans = ++gsize;
            }
            g[ans] = a[i];            // 1)
            idx[ans] = i;             // 2)
            pre[i] = idx[ans - 1];    // 3)
            f[i] = ans;               // 4)
        }
    }
    
    • 1)g[ans]g[ans]:长度为 ansans 的最长递增子序列最后一个值的最小值为 g[ans]g[ans]
    • 2)idx[ans]idx[ans]:配合 gg 数组记录下标;
    • 3)pre[i]pre[i]:第 ii 个数作为递增子序列的最后一个数,那么它的前驱是 pre[i]pre[i]
    • 4)f[i]f[i]:以 a[i]a[i] 结尾的最长递增子序列长度为 f[i]f[i]
    • 这样一来,我们就可以通过找到一个最大的 f[i]f[i],然后通过 pre[i]pre[i]pre[pre[i]]pre[pre[i]]pre[pre[pre[i]]]pre[pre[pre[i]]] 不断回溯找到最长递增子序列的一个任意可行解了。
    • 如何保证字典序最小呢?
    • 考虑当有两个下标 xxyy,满足 x<yx < yf[x]==f[y]f[x] == f[y] 时,哪个序列的字典序更小?我们可以从 a[x]a[x]a[y]a[y] 的值着手, 分三种情况讨论:
    • 1)a[x]==a[y]a[x] == a[y]:不影响结果,可以不讨论;
    • 2)a[x]<a[y]a[x] < a[y]:这种情况是不存在的,因为 a[y]a[y] 可以放在 a[x]a[x] 后面构成一个更长的序列,和 f[x]==f[y]f[x] == f[y] 矛盾;
    • 3)a[x]>a[y]a[x] > a[y]:这种情况下,a[y]a[y] 的字典序相对更小;
    • 所以,得出结论,逆序枚举找到最大的 f[i]f[i],然后通过路径回溯找到以 a[i]a[i] 结尾的最大递增子序列就是答案了。

    3、K 长单调子序列

    【例题6】给定数组 aa,设长度为 n(n1000)n(n \le 1000),求它的 k(k10)k(k \le 10) 长递增子序列的长度。

    • kk 优解问题和最优解问题类似,首先我们回到最原先的状态转移方程:f[i]=maxj=1i1(f[j]  aj<ai)+1f[i] = \max_{j=1}^{i-1} (f[j] \ | \ a_j < a_i) + 1
    • f[i]f[i] 表示以 aia_i 结尾的最长递增子序列的长度。
    • 那么对于 kk 优解问题,只需要在原有状态数组上增加一维,即用 f[n][k]f[n][k] 来表示状态,那么 f[i][0]f[i][0] 表示以 aia_i 结尾的最长递增子序列的长度,f[i][1]f[i][1] 表示以 aia_i 结尾的次长递增子序列的长度,… f[i][k1]f[i][k-1] 表示以 aia_i 结尾的 kk 长递增子序列的长度。
    • 状态转移方程变成:f[i][0...k1]=maxj=1i1(f[j][0...k1]  aj<ai)+1f[i][0...k-1] = \max_{j=1}^{i-1} (f[j][0...k-1] \ | \ a_j < a_i) + 1
    • 即从 (i1)k(i-1) k 个状态中挑出 kk 个最优状态,实现状态转移。
    • 时间复杂度为 O(n2k)O(n^2k)

    4、无序序列转换为递增序列

    【例题7】给定 n(n105)n(n \le 10^5) 个元素的数列 aa,你现在要求修改数量最少的元素,使得这个数列严格递增。其中无论是修改前还是修改后,每个元素都必须是整数。请输出最少需要修改多少个元素。

    • 这个问题相当于是要把一个无序的序列转换成一个严格递增的序列,求需要修改多少的元素。
    • 可以这么考虑,如果任意两个元素 aia_iaja_j,满足 i<ji < j,那么至少需要满足的是:ajaijia_j - a_i \le j - i 才能保证整个序列单调递增,所以我们将这个式子进行移项,得到:aiiajja_i - i \le a_j - j
    • bi=aiib_i = a_i - i,原式转换成:bibjb_i \le b_j
    • 于是,只需要求 bib_i 的最长单调不降子序列的长度即可,令答案为 ll,则原题的答案为 nln - l

    • 最长递增子序列的相关问题到这里就全部结束了,如果还有不懂的可以留言告诉作者。


    在这里插入图片描述


    六、最长单调子序列相关题集整理

    题目链接 难度 解析
    PKU 2533 Longest Ordered Subsequence ★☆☆☆☆ 【例题1】最长递增子序列 裸题
    HDU 1087 Super Jumping! Jumping! Jumping! ★☆☆☆☆ 最大递增子序列和
    HDU 1069 Monkey and Banana ★☆☆☆☆ 最大递增子序列和 + 全排列
    HDU 1160 FatMouse’s Speed ★☆☆☆☆ 最长递增子序列 任意解
    PKU 3903 Stock Exchange ★★☆☆☆ 【例题2】二分优化
    HDU 1025 Constructing Roads In JGShining’s Kingdom ★★☆☆☆ 二分优化
    HDU 1950 Bridging signals ★★☆☆☆ 二分优化
    HDU 5532 Almost Sorted Array ★★☆☆☆ 二分优化
    HDU 6197 array array array ★★☆☆☆ 二分优化
    HDU 5748 Bellovin ★★☆☆☆ 二分优化
    PKU 3670 Eating Together ★★☆☆☆ 二分优化
    PKU 1609 Tiling Up Blocks ★★☆☆☆ 二分优化
    HDU 1257 最少拦截系统 ★★☆☆☆ 【例题3】Dilworth定理
    HDU 2192 MagicBuilding ★★☆☆☆ Dilworth定理
    PKU 1065 Wooden Sticks ★★★☆☆ Dilworth定理
    HDU 2622 Everyone is No.1 ★★★☆☆ 【例题4】Dilworth定理
    PKU 1548 Robots ★★★☆☆ Dilworth定理
    NC91 最长递增子序列 ★★★☆☆ 【例题5】字典序最小解
    PKU 1836 Alignment ★★★☆☆ 线性扫描
    HDU 5773 The All-purpose Zero ★★★☆☆ 仔细思考 gg 数组含义
    HDU 3998 Sequence ★★★☆☆ 最长递增子序列 + 贪心 hash
    HDU 5087 Revenge of LIS II ★★★☆☆ 【例题6】次长递增子序列
    HDU 5256 序列变换 ★★★☆☆ 【例题7】思维转换
    HDU 5568 sequence2 ★★★☆☆ 递增子序列方案数
    HDU 4521 小明系列问题——小明序列 ★★★★☆ 线段树优化
    HDU 6284 Longest Increasing Subsequence ★★★★☆ 区间优化
    展开全文
  • 专题:最长单调子序列(LIS)问题 (4.27 记录) LIS问题是DP当中的一个很经典的问题。 LIS问题的核心在于状态的保护和转移。 一.LIS的长度 解法1:一般DP 时间复杂度O(n2) 很显然,对于某一个点i,1-i的最长单调子...

    专题:最长单调子序列(LIS)问题

    (4.27 记录)

    LIS问题是DP当中的一个很经典的问题。
    LIS问题的核心在于状态的保护和转移。

    一.LIS的长度
    解法1:一般DP 时间复杂度O(n2)
    很显然,对于某一个点i,1-i的最长单调子序列是唯一的,而以i结尾的最长单调子序列也是唯一的。这样就有思路:dp[i]表示以i结尾的最长单调子序列的长度。
    这两种思路唯一的区别在于dp是否要转移,或者更直观的来说,区别在于dp[n]是否就是最长单调子序列的长度。
    从A思路出发的话,1-i中的最长单调子序列长度一定不短于1-(i-1)的,所以初始情况下dp[i]=dp[i-1];从B思路出发的话,以i为结尾明显和以(i-1)结尾不是一回事,所以初始dp[i]=1.
    有递推式:
    dp[i] = max(dp[i],dp[j]+1) (i > j && a[i] > a[j])
    注意:由于dp[n] ≠ max,需要枚举一遍dp找max。

    解法2:队列伪模拟(或者说是贪心) 时间复杂度O(nlogn)
    这个办法跟DP我觉得是一点儿关系都没有。
    先给结论:维护一个单调的队列Q,记队尾为rear(初始为0),遍历a[i],如果a[i]<Q[rear]则入队,否则用a[i]替换掉Q中第一个不小于它的数。
    然后我们解释一下:
    现在假设我们维护的一个单调递增队列里面有三个数a,b,c,如果新增一个d,d>c,那么很显然这个队列就可以扩充。
    如果d<c,那么我们明确一下:我们现在维护的这个队列并不一定是真实的LIS,对于那个队列abc,其实b可以替换成任意一个(a,c)中的数,其他的数也同理。但是如果我们改的是队尾,很显然队尾越小越好,这样我们更有可能扩充这个序列的长度(靠替换那是没法扩充的),为了队尾越小越好,那前面的肯定也是越小越好,尽管这不是真实的,但是如果队尾真的更新了,那么真实的LIS也就变了;如果没有那就算了,反正我们压根就不关心到底队列里面是什么,我们只关心长度。
    大致如下(以单调递增为例):

    if(Q[rear} < a[i] Q[++rear] = a[i];
    else Q[find(a[i])] = a[i];
    

    (这个find里面怎么写,一会儿会讨论一下)

    二.LIS
    现在我们关心序列是什么了。
    从刚才已有的里面看一看:解法2不行,因为一个不真实的序列压根没用。
    所以我们就剩一个解法1可以改一改了。
    我们重复一遍解法1的核心:对于一个点i,以它为结尾的LIS唯一确定。
    这样一来,我们借鉴一下链表思想就行了,用head[x]记录以x为结尾的最长单调子序列的倒数第二个数,我们一直找head[x]并输出,就能得到一个真实的LIS。这种思想跟拓扑排序非常类似,至于拓扑,上一个记录已经写过了。
    由于这是一个LIS里面的重难点,给一个完整的板子:

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int head[100001],a[100001];
    void find(int x){
    	if(~head[x]) find(head[x]);
    	printf("%d ",a[x]);
    }
    int main(){
    	int n = 0,i,j,rear,telipu = -1,dp[100001];
    	memset(head,-1,sizeof(head));
    	while(scanf("%d",&a[++n]) != EOF);
    	--n;
    	for(i = 1;i <= n;i++) dp[i] = 1;
    	for(i = 2;i <= n;i++){
    		for(j = 1;j < i;j++){
    			if(a[j] < a[i] && dp[j] + 1 > dp[i]){//只留下更优的改变
    				dp[i] = dp[j] + 1;
    				head[i] = j;
    				if(telipu < dp[i]){
    					telipu = dp[i];
    					rear = i;
    				}
    			}
    			//dp[i] = max(dp[i],dp[j]);
    		}
    	}
    	printf("max=%d\n",telipu);
    	find(rear);
    	return 0;
    }
    

    彩蛋:(P1091 合唱队型)
    这题是一部分递增一部分递减,由于整个序列不变,所以预处理一边之后O(n)的找就行了。时间复杂度O(nlogn).
    讨论一下find:由于这题是严格单调,所以我们处理出来的队列里面也不应该有任何相等的数。这样一来,对于Q[mid]=a[i],应该把a[i]替换掉,所以判断条件带等。
    附上代码:

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int Q[1001],rear,n;
    int find(int x){
    	int l = 1,r = rear,mid;
    	while(l < r){
    		mid = (l + r) >> 1;
    		if(Q[mid] >= x) r = mid;
    		else l = mid + 1;
    	}
    	return l;
    }
    int main(){
    	int a[1001],b[1001],c[1001],i;
    	scanf("%d",&n);
    	memset(Q,-1,sizeof(Q)); 
    	for(i = 1;i <= n;i++) scanf("%d",&a[i]);
    	for(i = 1;i <= n;i++){
    		if(Q[rear] < a[i]) Q[++rear] = a[i];
    		else Q[find(a[i])] = a[i];
    		b[i] = rear;
    	}
    //---------------------------------------------------------
    	memset(Q,-1,sizeof(Q));
    	rear = 0;
    	for(i = n;i >= 1;i--){
    		if(Q[rear] < a[i]) Q[++rear] = a[i];
    		else Q[find(a[i])] = a[i];
    		c[i] = rear;
    		//printf("%d ",Q[rear]);
    	}
    	//printf("\n");
    	rear = 0;
    	for(i = 1;i <= n;i++){
    		rear = max(rear,b[i] + c[i] - 1);
    		//printf("%d %d\n",b[i],c[i]);
    	}
    	printf("%d\n",n - rear);
    	return 0;
    }
    /*
    10
    1 7 5 3 2 7 4 5 8 6
    */
    

    Thank you for reading!

    展开全文
  • 最长单调子序列求解

    千次阅读 2014-06-30 20:20:11
    本文给出了如下题目的参考解答,虽然方法并不是最优,但...题目:已知一个序列,由随机数构成,求其最长单调子序列。要求: 单调分严格和不严格两种情况,并分别求解并输出一个最长单调子序列和所有符合要求的子序列。
    

    本篇博文为追忆曾经写过的算法系列第三篇

    温故知新


    题目重述

    已知一个序列,由随机数构成,求其最长单调子序列。

    要求:单调分严格和不严格两种情况,并分别求解并输出一个最长单调子序列和所有符合要求的子序列。


    问题分析

    本题是求解有约束条件的子序列问题,可用动态规划求解。由于本题是求解最长单调子序列的,包括求一个最长单调子序列和求解所有符合要求的序列,下面将按照这两种情况讨论算法复杂度。


    求解一个最长单调子序列的算法复杂度

    本题假设单调为递增的情况,序列长度为N(任意大小),即序列S[N]。若采用直接搜索的方法,同时定义数组LP[N]记录对应序列元素所在最长单调子序列中的位置。其算法思想如下:序列从S[1]开始(S[0])已经初始化),每递增一个,判断与之前的每个数值的大小,若S[i]> S[j](j<i) (注:若非严格则是“>=”)LP[i]<=LP [j]+1,则更新LP[i]LP[j]+1。这样保证了每个元素归类到自身所满足的最长子序列当中,但此算法的复杂度为O(n^2)

    通过对第二层循环,即确定新加进的元素其所在最长子序列的位置,可改进搜索策略,将复杂度降低为O(nlogn)。基本思想是:定义数组Len[N+1],第0个元素空闲,第j(j>0)个位置存储所有长度为j的子序列中最后元素的最小值,这样可以保证当前序列为最长序列且保持局部最优。当对新添加的元素S[i]进行判别时,采用二分搜索法在Len数组中搜索元素的位置,由于Len一直保持升序排列,且搜索到其所在的位置后,取代比他大的元素,从而成为那个长度的序列最后元素最小,其搜索复杂度为O(logn)。在算上第一层循环的O(n),所以复杂度为O(nlogn)。通过LP[N]S[N]可循环求解出一个最长单调子序列,复杂度为O(n)。所以,总复杂度为O(nlogn)


    求解所有最长单调子序列的复杂度

    求解所有最长单调子序列,其和2.1中的唯一不同在于求解输出所有最长单调子序列,而求解LP[N]MaxLen的复杂度同2.1中的分析,最好方法的复杂度为O(nlogn)。输出所有最长单调子序列(设其复杂度为O(T))和上述过程是并列而非嵌套,所以总的复杂度为

    T的求解很容易,通过分析可以发现,其中第一个n指循环LP[N]得到最长子序列的起始位置,而k指所有最长子序列的个数,取小于号是因为最长序列的起始点总是小于n的。

    综上可以得到,求解所有最长单调子序列的复杂度为,其中k的取值为[0,n]。即极端情况下为O(n^2),这里之所以讨论是想强调无限长序列下有限个最长单调子序列的思想。



    算法思想与实现

    a.定义S[N]LP[N]Len[N+1]三个数组,其分别是序列本身,序列元素对应的最长子序列位置记录,长度为i的子序列最末元素的最小值。其中S[N]随机生成,Len[0]闲置;


    b.初始化LP[0]1S[N]i=1开始循环至N-1K用于记录Len的最大值,即目前搜索到的最长子序列长度,其初始值为K=1;若S[i]>Len[K] (注:若非严格则是“>=”),即下一个元素的值大于最长子序列最后元素的值,则直接将S[i]放在Len[++K]的位置;若S[i]<=Len[K],则进入步骤c;


    c.调用函数k = fn_InsertPos(),并执行如下操作: Len[k]=S[i]; LP[i] = k; LP[i]仍记录了S[i]所在的最长子序列位置,有利于序列的输出;fn_InsertPos()采用二分查找法,但和常规的查找条件不同,其算法复杂度为O(logn);


    d.S[i]的搜索后,Len所记录的k值即为最长单调子序列的长度,此时可通过LP[N ]数组的记录求出一个最长子序列,即从后向前遍历LP[N],用辅助数组P[N]记录子序列,k记录当前需要存入的子序列长度,当LP[i]==kS[i]<P[k](注:若非严格则是“>=”),将S[i]存入P[--k],直至k==0,具体过程可参见函数void fn_OutPutLMS(int Pos )其算法复杂度为O(n)


    e.要输出所有最长单调子序列,则需要确定所有最长子序列的末尾元素所在的位置,这个容易实现,即定义数组C[N],遍历LP[N]并记录值为MaxLen的元素的位置。然后一次调用voidfn_OutPutLMS(int Pos )复杂度为O(kn)


    程序实现

    /*-----------------------------------------------------------------
    *                    最长单调子序列问题 
    * -----------------------------------------------------------------
    *  By Gu Jinjin SEU
    *  求解最长单调子序列,分严格和不严格两种情况
    *  这里以单调递增为例
    *  Time : 2012/11/28-29   Weather:rainy
    */
    
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    
    using std::cout;
    using std::endl;
    // define 
    #define N 5000
    // S[N]-序列,LP[N]-序列元素在最长子序列中的位置
    // Len[N+1]-用于记录i长度的所有单调子序列末尾元素最小值
    int S[N],LP[N],Len[N+1];
    // 记录最长单调子序列长度
    int MaxLen; 
    
    // 函数声明
    void fn_RandNum();
    int fn_InsertPos(int Si, int K);
    int fn_GetLMS_Len();
    void fn_OutPutInitList();
    void fn_OutPutLMS(int Pos);
    void fn_GetAllLMSes();
    
    
    /*-----------------------------------------------------------------
    *                void main( void )
    * -----------------------------------------------------------------
    * 主函数
    */
    void main()
    {
    	clock_t t_start,t_end;
    	fn_RandNum();
        t_start=clock();
    	MaxLen = fn_GetLMS_Len();
    	t_end=clock();
    	cout<<"Inital List:"<<endl;
    	cout<<"=============================="<<endl;
    	fn_OutPutInitList();
    	cout<<"All LMSes:"<<endl;
    	cout<<"=============================="<<endl;
    	fn_GetAllLMSes();
    	cout<<"=============================="<<endl;
    	cout<<"The needed time:"<<difftime(t_end,t_start)<<"ms"<<endl;
    }
    
    /*-----------------------------------------------------------------
    *                void fn_RandNum( ... )
    * -----------------------------------------------------------------
    * 生成随机数
    */
    void fn_RandNum()
    {
    	// 用于保证是随机生成的数
    	// 不同的种子可以生成不同的随机数
    	//srand((unsigned)time(NULL)); 
    	for(int i=0; i<N; i++)
    	{
    		S[i] = rand()%N;
    		LP[i] = 1; // 数组初始化
    		Len[i] = 0;
    	}
    }
    
    /*-----------------------------------------------------------------
    *                void fn_InsertPos( ... )
    * -----------------------------------------------------------------
    * 计算元素所在的最长子序列中位置,并返回
    */
    int fn_InsertPos(int Si, int K)
    {
    	int low=1, high=K, mid; //定义上下界和中间值
    	mid=(low+high)/2;
    	// 若low>high,则说明搜索到
    	while(low <= high)
    	{
    		if(low > high)break;
    		else if(Len[mid]<Si)low = mid+1;
    		else high = mid -1;
    		mid=(low+high)/2;
    	}
    	//返回插入的位置,即S[i]元素所对应的最长子序列的长度
    	return(high+1);
    }
    
    /*-----------------------------------------------------------------
    *                void fn_GetLMS_Len( ... )
    * -----------------------------------------------------------------
    * 计算LMS的长度
    */
    
    int fn_GetLMS_Len()
    {
    	int lmn=1,k=1;
    	Len[k]=S[0];
    	for(int i=1; i<N; i++)
    	{
    		if(S[i]>Len[lmn])
    		{
    			Len[++lmn]=S[i];
    			LP[i]=lmn;
    		}
    		else
    		{
    			k = fn_InsertPos(S[i],lmn);
    			Len[k] = S[i];
    		    LP[i] = k;
    		}
    	}
    	return(lmn);
    }
    
    /*-----------------------------------------------------------------
    *                void fn_OutPutInitSeq( ... )
    * -----------------------------------------------------------------
    * 输出原始数列
    */
    void fn_OutPutInitList()
    {
    	cout<<"S"<<'\t'<<"LP"<<'\t'<<"Len"<<endl;
    	cout<<"------------------------------"<<endl;
    	for(int i=0; i<N; i++)
    	{
    		cout<<S[i]<<'\t'<<LP[i]<<'\t'<<Len[i]<<endl;
    	}
    }
    
    /*-----------------------------------------------------------------
    *                void fn_OutPutLMS( ... )
    * -----------------------------------------------------------------
    * 输出一个LMS函数
    */
    void fn_OutPutLMS(int Pos)
    {
    	int P[N],k=MaxLen-1;
    	P[k]=S[Pos];
    
    	for(int i=Pos-1; i>=0; i--)
    	{
    		if(LP[i] == k && S[i]< P[k])P[--k]=S[i];
    	}
    	// OutPut LMS
    	if(k==0)
    	{
    		for(int i=0; i<MaxLen; i++)cout<<P[i]<<'\t';
    		cout<<endl;
    		cout<<"------------------------------"<<endl;
    	}
    }
    
    /*-----------------------------------------------------------------
    *                void fn_GetAllLMSes( ... )
    * -----------------------------------------------------------------
    * 获取所有LMSes
    */
    void fn_GetAllLMSes()
    {
    	// C[N]用于记录长度为MaxLen序列的元素在LP[N]中位置
    	int C[N], k=0; 
    	for(int i=N-1; i>=MaxLen-1; i--)
    	{
    		if(LP[i]==MaxLen){ C[k]=i; k++;}
    	}
    	
    	for(int i=0;i<k;i++)
    	{
    		fn_OutPutLMS(C[i]);
    	}
    }
    

    结果(N取20的时候,其中数组为随机函数生成)


    
    展开全文
  • 用VC编写的控制台程序,用增量法求给定序列的最长单调子序列
  • 最长单调子序列(C语言)--动态规划

    千次阅读 2019-05-09 17:18:20
    最长单调子序列 题目描述 给出一个由n个数组成的序列x[1…n],找出它的最长单调上升子序列。 即求最大的m和a1,a2……,am,使得a1<a2<……<am且x[a1]<x[a2]<……<x[am] 解题思路 动态规划的状态...
  • 题意: 求所给出长度为 N 的最长上升子...设\(dp[i]\)表示以\(i\)结尾的最长单调子序列,那么当\(arr[i]>arr[j]时\) \(dp[i]=max(dp[j]+1,dp[i]) (j\in[1,i))\) #include <bits/stdc++.h> #define IOS io...
  • 给定一个序列,要求求出该序列的最长单调子序列, 即 longest increasing subsequence 这是一个经典的动态规划求解问题。 设给定序列为 a[],大小为 n,如何求其最长单调子序列呢? 考虑将最长单调子序列的长度...
  • 求解最长单调子序列.

    2016-09-17 12:19:23
    给定一个长度N的子序列,求出一个单调...假设result[k]是代表以第k个元素作为结尾的某一个单调子序列的长度,那么对于第k+1个元素结尾的单调子序列,可以这样计算result[k+1]=max(1+result[i])wherearray[i][k+1],ifrom0t
  • 最长单调递增子序列问题 问题描述 给定一个由n个数组成的序列,求出其最长的单调递增子序列的长度 例: 输入:1 6 7 8 2 3 3 5 该序列最长的单调递增子序列为1 ...设序列a1...ak−1a_1...a_{k-1}a1​...ak−1​的最长单
  • 最长单调子序列问题

    2015-11-28 10:19:46
    概念 序列的子序列,可以由从这个序列中去掉0个或多个元素而得来...两个序列最长的公共子序列就被称之为最长公共子序列最长公共子序列, 又被称之为最长公共子串,译自英文名Longgest Common Subsequence,可以缩
  • 最长单调子序列例题

    2019-04-11 15:18:00
    先排序,然后找最长单调子序列。 代码如下: #include #include #include #include using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxn=5*1e3+5; int t; int ...
  • 题意: 一个俱乐部有n个人, 每个人都有一个漂亮值和财富值。现在俱乐部要举办活动, 但是俱乐部中有些人是相互讨厌, 相互讨厌的人有两... 所以我们可以想到最长单调子序列, 这个就是多了一个条件的限制。我们可以
  • 问题:最长连续上升子序列长度,或者说最长连续单调子序列   代码及注释如下: def get_length(A): #f[i]表示以A[i]结尾的最长上升子序列的长度 n = len(A) #最终结果 res = 0 if n==0: return 0 f = [0...
  • 最长上升子序列(Longest Increasing Subsequence),简称LIS,也有些情况求的是最长非降序子序列,二者区别就是序列中是否可以有相等的数。 例如: 对于序列(1, 7, 3, 5, 9, 4, 8),我们就会得到一些上升的子序列,...
  • 首先来说子串和字符串的区别: 子串!=子序列 例如:一个字符串 awbcdewgh 他的子串: awbc.... 很多个子序列 但是子序列中的字符在字符串中不一定是连在一起的, 但是 子序列一定是单调的, (即字符之间
  • i]中,当以a[i]为单调递增子序列最后一个元素时,所得最长单调递增子序列的长度。状态转移方程:c[0]=1;c[i]=max{1,c[j]+1} a[j]&lt;a[i]&amp;&amp;j&lt;i;int LongestIncr(int X[], int n, int c...
  • 最长单调子序列(O(n^2) 和 O(nlg(n))))
  • 问题描述:给定某一组无序的数,求其中最长的单调序列的长度(该单调序列不一定是连续的),如在 5 6 1 2 4 7 5 中最长上升增序列是1 2 4 7 或者1 2 4 5。 该题可以用动态规划的方法解决,时间复杂度为O(n^2): ...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 141
精华内容 56
关键字:

最长单调子序列