首页 > 其他分享 >最长上升子序列总结

最长上升子序列总结

时间：2024-02-02 16:45:16浏览次数：34  
标签：总结 include int su 序列 上升 最长

这是最长上升子序列最基础的例子：
给定一串数字 3 2 4 5 1 那么他的最长上升子序列就是 3 4 5
其衍生问题为：

  • 求最长递减子序列、求正方向反方向最长递增/递减子序列
  • 求先上升后下降的最长子序列、
  • 求能完全覆盖整个序列的最小下降子序列个数
  • 求能完全覆盖整个序列的最小上升和下降子序列的和
  • 求最长上升子序列的和

LIS (最长上升子序列，Longest Increasing Subsequence)
LCS (最长公共子序列，Longest Common Subsequence)
LCIS (最长公共上升子序列，Longest Common Increasing Subsequence)

1. 求向左向右最长下降子序列长度

AcWing 1017. 怪盗基德的滑翔翼

给定一个数组，求向左或向右的最长下降子序列

输入格式

输入数据第一行是一个整数K，代表有K组测试数据。
每组测试数据包含两行：第一行是一个整数N，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h，按照建筑的排列顺序给出。

输出格式

对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。

数据范围
1≤K≤100,
1≤N≤100,
0
#include 
using namespace std;
const int N = 110;
int n;
int a[N], f[N];
int main()
{
    int K;
    cin >> K;
    while(K--)
    {
        cin >> n;
        for(int i = 1;i <=n; i++) cin >> a[i];
        int res = 0;

        //背两段正反上升子序列模版
        //正向求解LIS问题
        for(int i = 1; i <= n;i ++)
        {
            f[i] = 1;
            for(int j = 1; j < i; j ++)
                if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        //反向求解LIS问题
        for(int i = n; i >=1 ; i --)
        {
            f[i] = 1;
            for(int j = n; j > i ; j --)
                if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);  
        }
        cout << res << endl;
    }
    return 0;
}

2. 求先上升后下降的最长子序列

AcWing 1014. 登山

登山是先上山后下山求最大经过点数
可以思考为从peak分割，求左最长上升+右最长下降

输入格式

第一行包含整数N，表示景点数量。
第二行包含N个整数，表示每个景点的海拔。

输出格式

输出一个整数，表示最多能浏览的景点数。

数据范围
2≤N≤1000
输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
4

//先上升后下降，所以对于peak a[k]，向左向右各求最长下降子序列，也可以理解成反向上升
//所以就是a[1]到a[k-1]的最长上升子序列和a[n]到a[k-1]的最长上升子序列之和
#include 
#include 
using namespace std;
const int N = 1010;
int n;
int a[N], f[N], g[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[i] > a[j]) f[i] = max(f[i], f[j] + 1);
    }
    for(int i = n; i >= 1; i --)
    {
        g[i] = 1;
        for(int j = n; j >= i; j --)
            if(a[i] > a[j]) g[i] = max(g[i], g[j] + 1);
    }

    int res = 0;
    for(int i = 1; i <= n; i++)
        res = max(res, f[i] + g[i]-1);//要记得-1，peak是重合的
    cout << res;
    return 0;

}
AcWing 482. 合唱队行

给定一群人的身高，按中间高两边低站队，问多少人出列才能让剩下的人排成合法队形
意思就是问 挑出几个人才能满足合唱队列，和爬山一样的，只不过是输出剩下的

#include 
#include 
using namespace std;
const int N = 110;
int n;
int f[N], g[N], a[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[i] > a[j]) f[i] = max(f[i],f[j] + 1);
    }
    for(int i = n;i >= 1; i --)
    {
        g[i] = 1;
        for(int j = n; j >= i; j--)
            if(a[i] > a[j]) g[i] = max(g[i],g[j] + 1);
    }
    int res = 0;
    for(int i = 1;i <=n; i++) res = max(res, f[i]+g[i]-1);
    cout << n-res; //就这里不同
    return 0;

}

3. 实际问题抽象为最长上升子序列问题

AAcWing 1012. 友好城市

一条河南北两边有友好城市对
求航线不交叉的最大值
其实想一下，不交叉就是一侧排序，求另一侧上升子序列最大数

输入格式

第1行，一个整数N，表示城市数。
第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出格式

仅一行，输出一个整数，表示能批准的航道最多申请数。

数据范围
1≤N≤5000,
0≤Xi≤10000
输入样例：
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例：
4

//按一遍的城市排序，求另一边的最长上升子序列就是答案
#include 
#include 
using namespace std;
const int N = 5010;
int n;
int f[N];
typedef pair PII;
PII q[N];
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d%d", &q[i].first, &q[i].second);
    sort(q, q + n);

    for(int i = 0; i < n; i ++)
    {
        f[i] = 1;
        for(int j = 0; j < i;j ++)
            if(q[i].second > q[j].second) f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for(int i=0; i < n;i ++ ) res= max(res, f[i]);
    cout << res;
    return 0;

}

4. 最大上升子序列之和

AcWing 1016. 最大上升子序列和

比较简单，就是把求数量问题改为求和问题
把最长上升子序列的状态更新的+1改为+a[i]即可

#include 
#include 
using namespace std;
const int N = 10010;
int n;
int a[N], 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] = a[i];
        for(int j = 1; j 
#include 
using namespace std;
const int N = 1010;

int n;
int q[N];
int f[N], g[N];

int main()
{
    //第一题最长递减子序列模版
    while(cin >> q[n]) n ++;
    int res = 0;
    for(int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for(int j = 0; j < i;j ++ )
        {
            if(q[i] <= q[j]) f[i] = max(f[i],f[j] + 1);
        }
        res = max(res, f[i]);
    }

    cout << res << endl;

    //g存所有子序列末尾，cnt来存当前子序列的个数
    int cnt = 0;
    for(int i = 0; i < n; i ++)
    {
        int k = 0; //k是标号, 遍历所有序列
        //没有遍历完所有序列 && k序列的结尾小于当前数 那么k++，到下一个序列
        while (k < cnt && g[k] < q[i]) k ++ ;
        g[k] = q[i];    
        //这样的存法会让g中递增排序，因此需更新g[k]
        if (k >= cnt) //说明没有序列大于等于当前数，那么开一个新的序列
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

6.求能完全覆盖整个序列的最小上升和下降子序列的和

用up[k]和down[k]记录第k套上升（下降）系统目前所拦截的最后一个导弹
dfs(u,su,sd)意味着已有su个上升，sd个下降，正在处理第u个数
剩下的就是上一个题加深搜模版了，要注意恢复现场，分类讨论dfs的下一层情况

下面解释下存最长上升/下降子序列末尾的数组up[k], down[k]的原理：
例子：3， 2， 4， 3，求down
第一轮为[[3]]，第二轮为[[3,2]]，第三轮为[[3,2],[4]]，第四轮为[[3,2],[4,3]]。因此down为[2,3]
所以down的机制里永远是递增的末尾。up同理

AcWing 187. 导弹防御系统

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

输入格式

输入包含多组测试用例。
对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。
第二行包含 n 个不同的整数，表示每个导弹的高度。

当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。

输出格式
数据范围
1≤n≤50
输入样例：
5
3 5 2 4 1
0
输出样例：
2

#include 
#include 
using namespace std;
const int N = 55;
int n;
int q[N];
int ans;
//up[k]和down[k]数组存第k套(上升/下降)数组的最后一个子序列
int up[N], down[N];
//dfs(u,su,sd)意味着已有su个上升，sd个下降，正在处理第u个数
//dfs(第几颗导弹，最长上升子序列个数，最长下降子序列个数)
void dfs(int u, int su, int sd)
{
    //由于是深搜，为了筛去答案更差的结果，所以更差的就直接return不用算了
    if(su + sd >= ans) return;
    if(u == n)
    {
        //如果说u==n那么就找到了一种匹配的方法
        ans = su + sd;
        return;
    }
    //情况1：将当前数放到上升子序列中
    int k = 0;//用来遍历已存在的子序列尾
    while(k < su && up[k]>q[u]) k++;
    int temp = up[k];//临时备份up[k]
    up[k] = q[u]; //用当前数更新第k个上升子序列的末尾
    if(k < su) dfs(u + 1, su,sd);//k=su代表新开了一个数组
    up[k] = temp;//恢复现场

    //情况1：将当前数放到下降子序列中
    k = 0;
    while(k < sd && down[k]> n, n)
    {
        for(int i=0; i < n; i ++) cin >> q[i];

        ans = n;
        //更新ans来维护最小防御系统套数
        dfs(0,0,0);
        cout << ans << endl;
    }

    return 0;
}

7. 最长公共上升子序列

没弄懂这个题 参考题解 https://www.acwing.com/solution/content/52304/
状态表示：

  • f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合
  • f[i][j]的值等于该集合的子序列中长度的最大值

状态计算（对应集合划分）：
首先依据公共子序列中是否包含a[i]，将f[i][j]所代表的集合划分成两个不重不漏的子集：

  • 不包含a[i]的子集，最大值是f[i - 1][j]
  • 包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b[]中是哪个数：
    • 子序列只包含b[j]一个数，长度是1
    • 子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1(倒数第一个数b[j])
    • …
    • 子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1

如果直接按上述思路实现，需要三重循环，对应未优化的朴素算法

然后我们发现每次循环求得的maxv是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值。
因此可以直接将maxv提到第一层循环外面，减少重复计算，此时只剩下两重循环。

最终答案枚举子序列结尾取最大值即可。

AcWing 272. 最长公共上升子序列
输入格式

第一行包含一个整数 N，表示数列 A，B 的长度。
第二行包含 N 个整数，表示数列 A。第三行包含 N 个整数，表示数列 B。

输出格式

输出一个整数，表示最长公共上升子序列的长度。

数据范围
1≤N≤3000 ,序列中的数字均不超过 2^31−1。
输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2
朴素做法，未优化，会超时：
#include 
#include 
using namespace std;
const int N = 3010;
int n;
int a[N],b[N],f[N][N];
int main()
{
    cin >> n;
    for(int i = 1;i <=n ;i ++) cin >> a[i];
    for(int i = 1;i <=n ;i ++) cin >> b[i];
    //遍历所有状态
    for(int i = 1;i <=n; i ++)
        for(int j = 1;j <=n; j ++)
        {   
            //先给把b序列中的新值添加过来，直接继承即可
            f[i][j] = f[i-1][j];
            //按这样的状态表示方法，f[i][j-1]不一定存在
            if(a[i]==b[j])//只有在新添的结尾字符相同时才存在
            {
                f[i][j] = max(f[i][j], 1);//答案至少为1，且要是公共的，所以只能写在这里
                //把b[j]前的所有a遍历一遍,判断上升
                for(int k = 1;k < j; k++)
                    if(b[k] < b[j]) f[i][j] = max(f[i][j], f[i][k] + 1);
            }
        }

    int res = 0;//枚举最大时候让a全选，然后枚举max的b
    for(int i = 1; i <= n; i ++) res = max(res, f[n][i]);
    cout << res;
    return 0;
}
优化就是对代码做等价变形
#include 
#include 
using namespace std;
const int N = 3010;
int n;
int a[N],b[N],f[N][N];
int main()
{
    cin >> n;
    for(int i = 1;i <=n ;i ++) cin >> a[i];
    for(int i = 1;i <=n ;i ++) cin >> b[i];

    for(int i = 1;i <=n; i ++)
    {
        int maxv = 1;
        for(int j = 1;j <=n; j ++)
        {   
            f[i][j] = f[i-1][j];
            if(a[i] ==b[j]) f[i][j] = max(f[i][j], maxv);
            if(b[j] < a[i]) maxv = max(maxv, f[i][j] + 1);
        }
    }

    int res = 0;
    for(int i = 1; i <= n; i ++) res = max(res, f[n][i]);
    cout << res;
    return 0;
}

标签：总结,include,int,su,序列,上升,最长
From： https://www.cnblogs.com/BadBadBad/p/18003446/LIS-LCS-LCIS

相关文章

  • 2023 Airtest 年终总结来了，大佬们速来围观！
    此文章来源于项目官方公众号：“AirtestProject”版权声明：允许转载，但转载必须保留原链接；请勿用作商业或者非法用途1、前言马上要进入2024年龙年春节了~，~让我们回顾一下2023年里大家与AirtestProject一起成长的痕迹，也快来看看，在2024年，AirtestProject会有什么新的功能~2、开源产......
  • R语言时变向量自回归（TV-VAR）模型分析时间序列和可视化|附代码数据
    全文链接：http://tecdat.cn/?p=22350 最近我们被客户要求撰写关于时变向量自回归（TV-VAR）模型的研究报告，包括一些图形和统计输出。在心理学研究中，个人主体的模型正变得越来越流行。原因之一是很难从人之间的数据推断出个人过程另一个原因是，由于移动设备无处不在，从个人获得的时间......
  • Web2.5总结
    在交易和财富效用驱动的时代，Web3.0的“妥协方式”： DeFi，NFT和GameFi，甚至是Meme明显更加容易捕获新的用户，投资能够出圈，获得新流量的WEB3消费级应用成为投资热点。艺术领域，2021年，佳士得、苏富比两家传统拍卖行一共拍卖成交了2.5亿美元的NFT，其中6930万美元来自于Beeple的作......
  • 操作DOM常用的方法和属性总结
    document.querySelector()返回指定css选择器的第一个元素对象document.querySelectorAll()返回指定css选择器的所有元素对象textContent设置或获取元素中的文本内容style:display设置或获取元素的显示类型textAlign设置或获取文本对齐方式transform向元素应用2D或3D转换......
  • 2.1寒假每日总结23
    最最简单的超级马里奥训练过程fromnes_py.wrappersimportJoypadSpaceimportgym_super_mario_brosfromgym_super_mario_bros.actionsimportSIMPLE_MOVEMENTimporttimefrommatplotlibimportpyplotaspltfromstable_baselines3importPPOenv=gym_super_mario......
  • Codeforces Round 922 (Div. 2) 赛后总结
    自豪的是D题做出来了，悲哀的是B题没能做出来C题的绝对值最小D题，DP存不下状态就把状态放进所求值中比赛快结束的时候，我想，这个B题，它但凡需要我通过归并排序或者树状数组求逆序对，不比C题进制转化要难？于是我就猜了一个结论结论是对的，但不幸的是，我编程实现的时候出错了考虑怎样证......
  • 【技巧总结】java整数，字符串，数组之间的相互转换（持续更新）
    字符串转换为int类型给定一个字符串Stringstr="1234";转为转数字1234valueOf()Integernum=Integer.valueOf(str);返回的是包装类对象，可以进行调用对象方法可以用toString()方法。​parseIntintnum=Integer.parseInt(str)返回的是基本数据类型字符串......
  • Linux网络设备驱动总结
    1.Linux系统对网络设备驱动定义了4个层次，这4个层次为网络协议接口层、网络设备接口层、提供实际功能的设备驱动功能层和网络设备与媒介层。2.网络协议接口层向网络层协议提供统一的数据包收发接口，不论上层协议为ARP还是IP，都通过dev_queue_xmit()函数发送数据，并通......
  • 代码随想录算法训练营第九天| 28. 实现 strStr() 459.重复的子字符串 字符串总结 双
     28.实现strStr()给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从0开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。题目链接：28.找出字符串中第一个匹配项的下标-力扣（LeetCode）思路：标......
  • 如何做好一个信息系统项目经理，一个项目经理的个人体会和经验总结（三）
    前言今天我们继续聊聊在项目开发阶段，项目经理需要做好的事情......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99