正经夜光杯

这个屌丝很懒，什么也没留下！

热门标签

动态规划之线性DP入门——最长上升子序列模型_最长上升子序列dp思想

作者：正经夜光杯 | 2024-08-06 23:12:33

踩

最长上升子序列dp思想

基础：最长上升子序列，最长上升子序列优化（时间复杂度nlogn），最大上升子序列和，最长公共子序列

扩展/应用：怪盗基德的滑翔翼，登山，合唱队形，友好城市

进阶：最长公共上升子序列，拦截导弹，导弹防御系统

前言：

最长上升子序列可以说是最常见的dp了，所以它可以和一些思想结合或者优化它本身，题目变形也多，难度也会稍微高数字三角形模型，个人感觉。

ps：中间有些题在洛谷也有，洛谷数据是加强过的，所以如果该题洛谷有数据加强，我会附上思路，解释还有代码。

最长上升子序列

状态表示:
f(i)（一般情况一维序列用一维就行了）表示的集合：所有以a_i结尾的严格单调上升子序列
属性：求最长则是max
状态计算：
集合分类：要从倒数第二个数进行分类，因为倒数第一个数全部都是结尾，且必选，一定+1，但是倒数第二个数不一定！

所以将集合分成：
空（空就是只有一个数字）、a₁、a₂、a₃、a₄、…、a_i-1
注意
分析
设第k类中的上升子序列

....a[k] a[i]
....a[k] a[i]
....a[k] a[i]
1
2
3

a[i]>a[k]
1

左边的最大值是以a[k]结尾的最大值f[i]

f[i]=f[k]+1

所以
空（空就是只有一个数字）一定选 f(1)=1;
a₁ f(2)=f(1)+1
a₂ f(3)=f(2)+1
a₃ f(4)=f(3)+1
a₄ f(5)=f(4)+1
…
a_i-1 f(i)=f(i-1)+1

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e3+10;
int n;
int a[N];
int f[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++){
            if(a[j]<a[i])
                f[i]=max(f[i],f[j]+1);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,f[i]);
    cout<<res<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

怪盗基德的滑翔翼

分别求从左到右的最长上升子序列
然后求从右到左的最长上升子序列
取2种中间的最大值即可
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100+10;
int t,n;
int a[N];
int f[N];
int main(){
    cin>>t;
    while(t--){
        memset(a,0,sizeof a);
        memset(f,0,sizeof f);
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int res=0;
        for(int i=1;i<=n;i++){
            f[i]=1;
            for(int j=1;j<i;j++)
                if(a[j]<a[i])
                    f[i]=max(f[i],f[j]+1);
            res=max(res,f[i]);
        }
        for(int i=n;i>=1;i--){
            f[i]=1;
            for(int j=n;j>i;j--)
                if(a[j]<a[i])
                    f[i]=max(f[i],f[j]+1);
            res=max(res,f[i]);
        }
        cout<<res<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

登山

题目条件：
条件1:按照编号递增的顺序来浏览
条件2:不能连续浏览两个景点高度相同
条件3:一旦开始下降就不能上升
目标：求最多能浏览多少景点
思路：分别求从左到右的最长上升子序列和从右到左到最长上升子序列。
分别相加。
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000+10;
int n;
int a[N];
int f1[N],f2[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        f1[i]=1;
        for(int j=1;j<i;j++)
            if(a[j]<a[i])
                f1[i]=max(f1[i],f1[j]+1);
    }
    for(int i=n;i>=1;i--){
        f2[i]=1;
        for(int j=n;j>i;j--)
            if(a[j]<a[i])
                f2[i]=max(f2[i],f2[j]+1);
    }
    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,f1[i]+f2[i]-1);
    cout<<res<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

合唱队形
和登山类似
代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=100+10;
int a[N],dp1[N],dp2[N];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        dp1[i]=1;
        for(int j=1;j<i;j++)
            if(a[i]>a[j])
                dp1[i]=max(dp1[i],dp1[j]+1);
    }
    for(int i=n;i>=1;i--){
        dp2[i]=1;
        for(int j=n;j>i;j--)
            if(a[i]>a[j])
                dp2[i]=max(dp2[i],dp2[j]+1);
    }
    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,dp1[i]+dp2[i]-1);
    printf("%d\n",n-res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

最长上升子序列优化(nlogn)

nlogn的优化，实质是贪心+二分维护一个上升序列数组
思路：
维护一个上升序列数组b_i。
维护方法：如果要将原数组a_i接入b数组，使其成为最长上升子序列的话，就将a_i接入最大小于a_i的后面去(b_i>=a_i)

做法就是每次从b数组中找a_i能接入最大的小于a_i的后面（用二分）然后b数组长度+1，最小值更新成a_i。

举个例子
a数组：1 3 1 2 8 5 6
初始 b数组全是0，最长上升子序列长度 len=0，没有数字
step 1 将1加入b数组中，可是b数组中没有等于1或者更大的数字，故加入1，len++。
b ={1} len=1
step 2 将3加入b数组，可是b数组中没有等于3或者更大的数字，故加入3，len++。
b={1,3} len=2
step 3 将1加入b数组，二分找到b数组中有等于1的数字，替换，因为1=1所以不变，len不变
b={1,3} len=2;
step 4将2加入b数组，二分找到b数组中3是大于2且是最接近2的值，替换，len不变。
b={1,2} len=2;
step 5 将8加入b数组，可是b数组中没有等于8或者更大的数字，故加入8，len++。
b={1,2,8} len=3;
step 6 将5加入b数组，二分找到b数组中8是大于5且是最接近5的值，替换，len不变。
b={1,2,5} len=3;
step 7 将6加入b数组，可是b数组中没有等于6或者更大的数字，故加入6，len++。
b={1,2,5,6} len=4
所以a数组的最长上升子序列长度等于4
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;
int a[N],b[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int len=0;
    for(int i=1;i<=n;i++){
        int l=0,r=len;
        while(l<r){
            int mid=l+r+1>>1;
            if(b[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len,l+1);
        b[l+1]=a[i];
    }
    cout<<len<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

二分函数版本

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;
int a[N],b[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int len=0;
    memset(b,-0x3f,sizeof b);
    for(int i=1;i<=n;i++){
        if(a[i]>b[len]) b[++len]=a[i];
        else if(a[i]<b[len]){
            *lower_bound(b+1,b+len+1,a[i])=a[i];
        }
    }
    cout<<len<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

友好城市

acwing小数据版本(N=5000)
条件1:每个城市只能建立一座桥
条件2:所有桥与桥之间不能相交
目标：最多可以建立多少座桥
通过题意发现，所有合法的建桥方式就是上升子序列。
所以每一种合法的建桥方式都是一种上升子序列（城市数就等于上升子序列的长度）
所以所有合法的建桥方式的最大值也对应上升子序列的最大值长度最大值

所以先按照自变量的值将因变量进行排序，然后在排完序后的序列中求最长上升子序列
代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e3+10;
int dp[N];
int n;
struct City{
    int begin;
    int end;
}city[N];
bool cmp(City x,City y){
    return x.begin<y.begin;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&city[i].begin,&city[i].end);
    sort(city+1,city+1+n,cmp);
    int res=0;
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(city[i].end>city[j].end)
                dp[i]=max(dp[i],dp[j]+1);
        }
        res=max(res,dp[i]);
    }
    printf("%d\n",res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

洛谷大数据版本(N=200000)
思路都一样，就是需要nlogn的优化

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e3+10;
int b[N];
int n;
struct City{
    int begin;
    int end;
}city[N];
bool cmp(City x,City y){
    return x.begin<y.begin;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&city[i].begin,&city[i].end);
    sort(city+1,city+1+n,cmp);
    int len=0;
    for(int i=1;i<=n;i++){
        if(b[len]<city[i].end) b[++len]=city[i].end;
        else if(b[len]>city[i].end)
            *lower_bound(b+1,b+1+len,city[i].end)=city[i].end;
    }
    printf("%d\n",len);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

最长上升子序列和

状态表示：
集合：所有以a_i结尾的上升子序列
属性：和的最大值max
状态计算：
将f集合划分为(以倒数第二位划分)
空（空就是只有一个数字）、a₁、a₂、a₃、a₄、…、a_i-1
设第k类中的上升子序列

....a[k] a[i]
....a[k] a[i]
....a[k] a[i]
1
2
3

a[i]>a[k]
1

类似上面最长上升子序列f(k)+a[i]
所以
空 f[1]=a[1]
a₁ f[2]=f[1]+a[2]
a₂ f[3]=f[2]+a[3]
a₃ f[4]=f[3]+a[4]
a₄ f[5]=f[4]+a[5]
…
a_i-1 f[i]=f[i-1]+a[i]

转移方程类似上升子序列，只是不是+1而是+a[i]

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1010;
int a[N];
int dp[N]; 
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int res=0;
    for(int i=1;i<=n;i++){
        dp[i]=a[i];
        for(int j=1;j<i;j++)
            if(a[i]>a[j])
                dp[i]=max(dp[i],dp[j]+a[i]);
        res=max(res,dp[i]);
    }
    printf("%d",res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

拦截导弹

acwing小数据范围（N=1000）
这题第一问就是裸的最长上升子序列，直接写就行了
第二问是贪心。
贪心流程：
从前往后扫描每个数，对于每个数：
情况1:如果现有的子序列的结尾都小于当前数，则创建新子序列。
情况2:将当前数放到结尾大于等于它的最小的子序列后面。
发现了吗？这个思想不就是贪心接发的最长的上升子序列吗？

代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1010;
int a[N],b[N];
int dp[N];
int n;
int main(){
    while(~scanf("%d",&a[++n]));
    n--;
    int res=0;
    for(int i=n;i>=1;i--){
        dp[i]=1;
        for(int j=n;j>i;j--)
            if(a[i]>=a[j])
                dp[i]=max(dp[i],dp[j]+1);
        res=max(res,dp[i]);
    }
    int len=0;
    for(int i=1;i<=n;i++){
        int l=0,r=len;
        while(l<r){
            int mid=l+r+1>>1;
            if(b[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len,l+1);
        b[l+1]=a[i];
    }
    printf("%d\n%d\n",res,len);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

洛谷大数据范围（N=100000）

注意原来我们是如果找到与插入值相等时，就替换，替换了相当于没变，但是，第一问可以相等，所以二分时候不能替换相等的值，要找到后面比它大的值替换
代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N];
int n;
int main(){
    while(~scanf("%d",&a[++n]));
    n--;
    int res=0;
    for(int i=n;i>=1;i--){
        int l=0,r=res;
        while(l<r){
            int mid=(l+r+1)/2;
            if(c[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        while(c[l+1]==a[i]) l++;
        res=max(res,l+1);
        c[l+1]=a[i];
    }
    int len=0;
    for(int i=1;i<=n;i++){
        int l=0,r=len;
        while(l<r){
            int mid=(l+r+1)/2;
            if(b[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len,l+1);
        b[l+1]=a[i];
    }
    printf("%d\n%d\n",res,len);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

导弹防御系统

此题有两种情况，贪心只能确定一种，故不能贪心，只能爆搜。
N=50，n*2的n次方，硬爆搜超时，需要爆搜剪枝。

这道题步骤 dfs求最小步数->剪枝->求最小上升或者下降子序列的个数

dfs求最小步数有两种方法：1.迭代加深2.记一个全局最小值

这一题我的dfs写法是记一个全局最小值
保存下降或者上升子序列，通过二分优化最长上升子序列的方法，保存。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50+10;
int a[N],up[N],down[N];//up是上升子序列数组，down是下降子序列数组
int n,ans;
void dfs(int k,int up_len,int down_len){
    if(up_len+down_len>=ans) return ;//剪枝条件
    if(k==n){
        ans=min(ans,up_len+down_len);//更新最小值
        return ;
    }
    int i;
    for(i=1;i<=up_len;i++)
        if(up[i]<a[k]) break;//找到一个小于a[k]的up数组的下标
    int temp=up[i];//暂存它，回溯时方便回溯
    up[i]=a[k];//更新小于a[k]的数组
    dfs(k+1,max(up_len,i),down_len);
    up[i]=temp;//回溯
    for(i=1;i<=down_len;i++)
        if(down[i]>a[k]) break;//找到一个大于a[k]的down数组的下标
    temp=down[i];
    down[i]=a[k];
    dfs(k+1,up_len,max(down_len,i));
    down[i]=temp;
}
int main(){
    while(scanf("%d",&n)&&n!=0){
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        ans=100;
        dfs(1,0,0);
        printf("%d\n",ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

最长公共子序列

状态表示：
一般两个序列就用二维
集合：所有在第一个序列的前i个字母中出现且在第二个序列的前j个字母中出现的子序列
属性：max
状态计算：
可以根据选与不选划分为4种集合
1.
不选a_i
不选b_i
方程就是f(i-1,j-1) 一般都不写，因为下面三个都包含了它
2.
不选a_i
选b_i
方程就是f(i-1,j)
3.
选a_i
不选b_i
方程就是f(i,j-1)
4.
选a_i
选b_i
方程就是f(i-1,j-1)+1
代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int dp[N][N];
char a[N],b[N];
int n,m;
int main(){
    scanf("%d %d",&n,&m);
    scanf("%s %s",a+1,b+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
        }
    }
    printf("%d\n",dp[n][m]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最长公共上升子序列

这道题是最长公共子序列和最长上升子序列的完美结合
LIS与LCS的完美结合

状态表示： f(i,j)二维表示
集合：所有由第一个序列的前i个字母和第二个序列的前j个字母构成的且以b[j]结尾的公共上升子序列。(a[i]与b[j]对称)
属性：max

状态计算：
先将f划分为两个大集合：左边是所有包含a[i]的公共上升子序列，右边是所有不包含a[i]的公共上升子序列。

我们首先来看右边，所有不包含a[i]的公共上升子序列方程很简单就是f(i-1,j)

左边，它肯定是满足最长上升子序列的，所有我们将左边集合拆分成最长上升子序列的小集合
包含a[i]的上升子序列，因为a[i]与b[j]对称,a[i]=b[j]
将f左集合划分为(以倒数第二位划分)
空（空就是只有一个数字）、b₁、b₂、b₃、b₄、…、b_i-1
设第k类中的上升子序列

....b[k] b[j]
....b[k] b[j]
....b[k] b[j]
1
2
3

所以左边集合先求一个最长上升子序列的最大值。
代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=3010;
int a[N],b[N];
int dp[N][N];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=dp[i-1][j];
            if(a[i]==b[j]){
                int maxnumber=1;
                for(int k=1;k<j;k++){
                    if(a[i]>b[k])
                        maxnumber=max(maxnumber,dp[i-1][k]+1);
                }
                dp[i][j]=max(dp[i][j],maxnumber);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dp[n][i]);
    printf("%d\n",res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

N=3000，3层for，n的3次方，肯定超时。
DP->先找状态表示，状态计算->DP优化：DP优化一般对代码进行等价变形
故只需要将代码第二层和第三层进行等价变形即可
代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=3010;
int a[N],b[N];
int dp[N][N];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        int maxnumber=1;
        for(int j=1;j<=n;j++){
            dp[i][j]=dp[i-1][j];
            if(a[i]==b[j]) dp[i][j]=max(dp[i][j],maxnumber);
            if(a[i]>b[j]) maxnumber=max(maxnumber,dp[i-1][j]+1);//a[i]已经被占用所以只能从a[1]~a[i-1]种选择
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dp[n][i]);
    printf("%d\n",res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

到这里就结束啦～
欢迎有问题就在评论区指出，我们一起进步

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】