DP——最长上升子序列（LIS）

基本定义:

一个序列中最长的单调递增的子序列，字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。

LIS长度的求解方法：

1.$N^2$递推

动态规划一般的思考方式就是考虑将一个大问题分解成若干个小问题来求解，而小问题之间又有共同的求解方法，

或考虑当前状态与哪一个状态有关，并考虑如何转移。

那来思考以第$i$个数字为结尾的LIS是由哪一个转移过来的，显然肯定是由$1...i-1$转移过来的

每次都向前找比它小的和比它大的位置，将第一个比它大的替换掉，这样操作虽然LIS序列的具体数字可能会变，但是很明显LIS长度还是不变的

代码实现

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <cmath>

#define N 101101

using namespace std;

int a[N],f[N];

int n,ans=-;

int main() {

    scanf("%d",&n);

    for(int i=; i<=n; i++) {

        scanf("%d",&a[i]);

        f[i]=;

    }

    for(int i=; i<=n; i++)

        for(int j=; j<i; j++)

            if(a[j]<a[i]) f[i]=max(f[i],f[j]+);

    for(int i=; i<=n; i++)

        ans=max(ans,f[i]);

    printf("%d\n",ans);

    return ;

}

2.$N$$logN$贪心+二分

新建一个数组$dp$,$dp[i]$表示长度为i的LIS结尾元素的最小值。

对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。

因此，我们只需要维护$dp$数组，对于每一个$a[i]$，如果$a[i] > $dp$[当前最长的LIS长度]，就把$a[i]$接到当前最长的LIS后面，即$dp$ [++当前最长的LIS长度]=a[i]$。

那么如何维护$dp$数组呢？

对于每一个$a[i]$，如果$a[i]$能接到LIS后面，就接上去；否则，就用$a[i]$取更新$dp$数组。具体方法是，在$dp$数组中找到第一个大于等于$a[i]$的元素$dp[j]$，用$a[i]$去更新$dp[j]$。如果从头到尾扫一遍$dp$数组的话，时间复杂度仍是$O(n^2)$。我们注意到$dp$数组内部一定是单调不降的，所有我们可以二分$dp$数组，找出第一个大于等于$a[i]$的元素。二分一次$dp$数组的时间复杂度的$O(lgn)$，所以总的时间复杂度是$O(nlogn)$。

代码实现

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <cmath>

#define N 101101

using namespace std;

int a[N],dp[N];

int n,len;

int ef(int w){

    int l=,r=len,mid;

    while(l<=r){

        mid=(l+r)/;

        if(dp[mid]>=w) r=mid-;

        else l=mid+;

    }return l;

}

int main() {

    scanf("%d",&n);

    for(int i=; i<=n; i++)

        scanf("%d",&a[i]);

    for(int i=; i<=n; i++){

        if(a[i]>dp[len]) dp[++len]=a[i];//若a[i]>=dp[len]，直接把a[i]接到后面

        else dp[ef(a[i])]=a[i];//反之将a[i]替换成第一个>=a[i]的dp[x]

    }

    printf("%d\n",len);

    return ;

}

其实C++里面的有一个函数可用代替二分，那就是——$lower _ bound( )$函数。查找第一个大于等于该元素的位置。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <cmath>

#define N 101101

using namespace std;

int a[N],dp[N];

int n,len;

int main() {

    scanf("%d",&n);

    for(int i=; i<=n; i++)

        scanf("%d",&a[i]);

    for(int i=; i<=n; i++){

        if(a[i]>dp[len]) dp[++len]=a[i];

        else{

            dp[lower_bound(dp+,dp++len\,a[i])-dp]=a[i];

        }

    }

    printf("%d\n",len);

    return ;

}

$NlogN$树状数组维护

彩蛋：

LCS例题讲解：

P1439 【模板】最长公共子序列

题目描述

给出1-n的两个排列P1和P2，求它们的最长公共子序列。

输入输出格式

输入格式：

第一行是一个数n，

接下来两行，每行为n个数，为自然数1-n的一个排列。

输出格式：

一个数，即最长公共子序列的长度

输入输出样例

输入样例#1： 复制

5

3 2 1 4 5

1 2 3 4 5
输出样例#1： 复制

3

说明

【数据规模】

对于50%的数据，n≤1000

对于100%的数据，n≤100000

$N^2$解法：

我们可以用$dp[i][j]$来表示第一个串的前ii位，第二个串的前j位的LCS的长度，那么我们是很容易想到状态转移方程的：

如果当前的$A[i]$和$B[j]$相同（即是有新的公共元素） 那么

$dp[ i ] [ j ] = max(dp[ i ] [ j ], dp[ i-1 ] [ j-1 ] + 1);$

如果不相同，即无法更新公共元素，考虑继承：

$dp[ i ] [ j ] = max(dp[ i-1 ][ j ] , dp[ i ][ j-1 ])$

#include<iostream>

#include<cstdio>

#define N 1010

using namespace std;

int T,a[N],b[N],dp[N][N],n,m;

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    for(int i=;i<=n;i++) scanf("%d",&b[i]);

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            dp[i][j]=max(dp[i][j-],dp[i-][j]);

            if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-][j-]+);

        }

    }

    printf("%d\n",dp[n][m]);

    return ;

}

$NlogN$ 做法：

利用全排列的性质，因为两个序列都是$1~n$的全排列，那么两个序列元素互异且相同，也就是说只是位置不同罢了，那么我们通过一个map数组将A序列的数字在BB序列中的位置表示出来,

因为最长公共子序列是按位向后比对的，所以a序列每个元素在b序列中的位置如果递增，就说明b中的这个数在a中的这个数整体位置偏后,那么问题就转化成了求LIS

#include<iostream>

#include<cstdio>

#define N 101000

using namespace std;

int len,a[N],b[N],dp[N],n,mp[N];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i]),mp[a[i]]=i;

    for(int i=;i<=n;i++) scanf("%d",&b[i]);

    for(int i=;i<=n;i++){

        if(mp[b[i]]>dp[len]) dp[++len]=mp[b[i]];

        else{

            int l=,r=len,mid;

            while(l<=r){

                mid=(l+r)/;

                if(dp[mid]>=mp[b[i]]) r=mid-;

                else l=mid+;

            }dp[l]=mp[b[i]];

        }

    }

    printf("%d\n",len);

    return ;

}

下面是上面两个的结合：LCIS

1408 最长公共子序列 || 2185 最长公共上升子序列

题目描述 Description

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。
小沐沐说，对于两个串A，B，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。

输入描述 Input Description

第一行N，表示A，B的长度。
第二行，串A。
第三行，串B。

输出描述 Output Description

输出长度

样例输入 Sample Input

4
2 2 1 3
2 1 2 3

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

1<=N<=3000，A，B中的数字不超过maxlongint

算法分析：

定义状态：

$F[i][j]$表示以a串的前i个整数与b串的前j个整数且以b[j]为结尾构成的LCIS的长度。

状态转移方程：

①$F[i][j] = F[i-1][j]$     (a[i] != b[j])

②$F[i][j] = max(F[i-1][k]+1,F[i][j])$     (1 <= k <= j-1 && b[j] > b[k])

设计原理：

对于①，因为$F[i][j]$是以$b[j]$为结尾的LCIS，如果$F[i][j]>0$那么就说明$a[1]..a[i]$中必然有一个整数$a[k]$等于$b[j]$,因为$a[k]!=a[i]$，那么$a[i]$对$F[i][j]$没有贡献，于是我们不考虑它照样能得出F[i][j]的最优值。所以在a[i]!=b[j]的情况下必然有$F[i][j]=F[i-1][j]$。（显然）

对于②，前提是$a[i] == b[j]$,我们需要去找一个最长的且能让$b[j]$接在其末尾的LCIS。之前最长的LCIS在哪呢？首先我们要去找的F数组的第一维必然是$i-1$。因为i已经拿去和$b[j]$配对去了，不能用了。并且也不能是$i-2$，因为$i-1$必然比$i-2$更优。第二维呢？那就需要枚举$b[1]...b[j-1]$了，因为你不知道这里面哪个最长且哪个小于$b[j]$。这里还有一个问题，可不可能不配对呢？也就是在$a[i]==b[j]$的情况下，需不需要考虑$F[i][j]=F[i-1][j]$的决策呢？答案是不需要。因为如果$b[j]$不和$a[i]$配对，那就是和之前的$a[1]...a[i-1]$配对（假设$F[i-1][j]>0$，等于0不考虑），这样必然没有和$a[i]$配对优越。（为什么必然呢？因为$b[j]$和$a[i]$配对之后的转移是$max(F[i-1][k])+1$，而和之前的i`配对则是$max(F[i`-1][k])+1$）。

朴素的LCIS算法实现

以Hdu 1423 Greatest Common Increasing Subsequence为例。

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 3005

using namespace std;

int n,a[N],b[N],f[N][N],T,m,ans;

int main()

{

    scanf("%d",&T);

    while(T--){

        memset(f,,sizeof(f));

        scanf("%d",&n);

        for(int i=;i<=n;i++) scanf("%d",&a[i]);

        scanf("%d",&m);

        for(int i=;i<=m;i++) scanf("%d",&b[i]);

        for(int i=;i<=n;i++){

            for(int j=;j<=m;j++){

                f[i][j]=f[i-][j];//a[i]!=b[j]

                if(a[i]==b[j]){

                    int MAX=;

                    for(int k=;k<=j-;k++){

                        if(b[j]>b[k])

                            MAX=max(MAX,f[i-][k]);

                    }

                    f[i][j]=MAX+;

                }

            }

        }

        ans=;

        for(int i=;i<=m;i++) ans=max(ans,f[n][i]);

        printf("%d\n",ans);

        if(T) printf("\n");

    }

    return ;

}

从状态转移方程以及上述核心代码不难看到，这是一个时间复杂度为O(n^3)的DP，离平方还有一段距离。

但是，这个算法最关键的是，如果按照一个合理的递推顺序，max(F[i-1][k])的值我们可以在之前访问F[i][k]的时候通过维护更新一个max变量得到。怎么得到呢？首先递推的顺序必须是状态的第一维在外层循环，第二维在内层循环。也就是算好了F[1][len(b)]再去算F[2][1]。
如果按照这个递推顺序我们可以在每次外层循环的开始加上令一个max变量为0，然后开始内层循环。当a[i]>b[j]而且max<f[i-1][j]的时候令max=F[i-1][j]。如果循环到了a[i]==b[j]的时候，则令F[i][j]=max+1。
最后答案是$F[len(a)][1]..F[len(a)][len(b)]$的最大值。

#include<iostream>

#include<cstdio>

#define N 3005

using namespace std;

int n,f[N][N],a[N],b[N];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    for(int i=;i<=n;i++) scanf("%d",&b[i]);

    int maxn;

    for(int i=;i<=n;i++){

        maxn=;

        for(int j=;j<=n;j++){

            f[i][j]=f[i-][j];

            if(a[i]>b[j]&&maxn<f[i-][j]) maxn=f[i-][j];

            if(a[i]==b[j]) f[i][j]=maxn+;

        }

    }

    maxn=;

    for(int i=;i<=n;i++) if(f[n][i]>maxn) maxn=f[n][i];

    printf("%d\n",maxn);

    return ;

}

优化1

可以发现，其实上面的代码有些地方与0/1背包很相似，即每次用到的只是上一层循环用到的值，即f[i-1][j]，那么我们可以像优化0/1背包问题利用滚动数组来优化空间。

代码实现：

void dp()

{

    init();

    for(int i = ; i <= n; i++)

    {

        int MAX = ;

        for(int j = ; j <= n; j++)

        {

            if(a[i] > b[j]) MAX = max(MAX, f[j]);

            if(a[i] == b[j]) f[j] = MAX+;

        }

    }

    int ans = ;

    for(int j = ; j <= m; j++) ans = max(ans, f[j]);

    printf("%d\n", ans);

}

借鉴博课1 借鉴博客2

最新文章

  1. Java中堆的实现类PriorityQueue队列接口Queue
  2. Linux/Windows下如何退出telnet
  3. shell脚本实现数据库自动备份和删除备份
  4. linux内核分析课程笔记（二）
  5. Rails--%w用法[转]
  6. 在CentOS之上搭建VMware Player 7
  7. Spring中DispacherServlet、WebApplicationContext、ServletContext的关系
  8. Python基础学习笔记（一）入门
  9. SwithAndActivity 选择开关和活动指示
  10. 居然因为交换错了好几把。。。。，还有坑点是num1可以大于num2
  11. [2015-11-10]iis远程发布配置
  12. 201521123068《Java程序设计》第3周学习总结
  13. Spring知识整理
  14. Bzoj4566：[HAOI2016]找相同字符
  15. React-native完整配置流程
  16. FireMonkey 源码学习（4）
  17. 為什麼gnome-terminal中不能使用ctrl_shift_f來進行查找? 是因為 跟输入法的全局设置衝突了!
  18. Java03-Java语法基础（二）运算符
  19. js 标准对象
  20. serialize()传值缺失

热门文章

  1. 使用openstack的虚拟机模版注意事项
  2. 日常工作中常见的mysql优化技巧
  3. node.js中的require
  4. Visual Studio AI
  5. codevs1993 草地排水（最大流）
  6. Fib(兔子问题)python实现多种方法
  7. 【洛谷3224/BZOJ2733】[HNOI2012]永无乡 (Splay启发式合并)
  8. Codeforces 825D 二分贪心
  9. 题解报告：hdu 1272 小希的迷宫
  10. 去掉myeclipse的预览窗口