首页 > 其他分享 >最长公共上升子序列

最长公共上升子序列

时间:2024-03-20 11:56:14浏览次数:26  
标签:int res 公共 序列 include 最长

\(reference\)

\(problem\)

首先考虑最长公共子序列,需要两维数组,最长上升子序列,需要一维数组
由于最长公共子序列满足两个子序列相同,因此我们可以将二维数组的一维拿出来当作最长上升子序列的一维使用
故定义 \(f[i][j]\):以 \(b[j]\) 结尾的最长公共上升子序列

状态转移:由于b[j]必须有,因此我们可以枚举a[i]选不选
1. 选a[i]: f[i][j]=f[i-1][j]
2. 不选a[i]: if(a[i]==b[j])  f[i][j]=f[i-1][k]
  枚举可能的k
  for(i=1 to j-1)
    if(b[i]<b[j])
      f[i][j]=f[i-1][k] 

\(O(N^3)\) 做法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3010;

int n, a[N], b[N];
int f[N][N];// f[i][j]以b[j]结尾的最长公共上升子序列的长度

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )   cin >> a[i];
    for(int i = 1; i <= n; i ++ )   cin >> b[i];
    
    int res = 0;
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= n; j ++ )
        {
            // 不选 a[i]
            f[i][j] = f[i - 1][j];
            // 选 a[i]
            if(a[i] == b[j])
            {
                // 前一个 b[k]
                for(int k = 0; k < j; k ++ )
                    if(b[k] < b[j])
                        f[i][j] = max(f[i][j], f[i - 1][k] + 1);
            }
            res = max(res, f[i][j]);
        }
    }
    // 注意最优解不一定以b[n]结尾
    cout << res << endl;
    return 0;
}

\(O(N^2)\) 做法
优化第三维枚举 \(k\) 的过程,我们发现,第三维循环每次都要求得满足 b[k]<b[j]f[i-1][k] + 1 的最大值,因此我们可以把这个最大值提出来。
又因为,当需要枚举 \(k\) 时,一定有 b[j]==a[i],那么可以转化为维护 b[k]<a[i]f[i-1][k] + 1 最大值,由于 \(i\) 处于第一层不变,那么就很好维护了。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3010;

int n, a[N], b[N];
int f[N][N];// f[i][j]以b[j]结尾的最长公共上升子序列的长度

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )   cin >> a[i];
    for(int i = 1; i <= n; i ++ )   cin >> b[i];
    
    int res = 0;
    for(int i = 1; i <= n; i ++ )
    {
        int maxn = 1;
        for(int j = 1; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if(a[i] == b[j])    f[i][j] = max(maxn, f[i][j]);
            if(a[i] > b[j]) maxn = max(maxn, f[i - 1][j] + 1);
            res = max(res, f[i][j]);
        }
    }
    // 注意最优解不一定以b[n]结尾
    cout << res << endl;
    return 0;
}

标签:int,res,公共,序列,include,最长
From: https://www.cnblogs.com/ALaterStart/p/18084909

相关文章

  • C# 中使对象序列化/反序列化 Json 支持使用派生类型以及泛型的方式
    C#中使对象序列化/反序列化Json支持使用派生类型以及泛型方式废话#前言#为啥想写这个博客最近自己写的框架有用到这个类似工作流,支持节点编码自定义,动态运行自定义.尽量减少动态解析这就需要确定类型.有什么好的奇思妙想可以一起来讨论噢(现在还是毛坯,测......
  • 最长公共子序列求方案数
    题目链接参考在最长公共子序列问题中,状态的划分有两类:a[i]==b[j]f[i][j]=f[i-1][j-1]+1;a[i]!=b[j]f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1])不过,考虑到f[i-1][j-1]可以通过f[i-1][j]或f[i][j-1]转移而来,我们通常将a[i]!=b[j]时的转移方程写为f[i][j]=max(f[i-1][......
  • 51nod2599 最近公共祖先LCA
    给定一颗n个节点的树,根节点编号为1,有Q组询问,每次给定一对节点编号(x,y),求(x,y)的最近公共祖先。求LCA有多种方法,这里给的是倍增法,预处理时间O(nlogn),单次查询时间O(logn),支持在线。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definerep(i,a,b)for......
  • 蓝桥杯题目-可构造的序列总数
    链接可构造的序列总数-蓝桥云课(lanqiao.cn)知识点动态规划思路        定义表示序列长度为,以结尾的合法序列的数量 ,初始化时有。因为题意要求 是 的倍数,所以在转移时每个数应该从它的因子转移过来,即:                        ......
  • Prufer序列
    基本信息定义:prufer序列是无根树和序列的双向映射,并且描述了节点读书以及父节点的信息。使用场景:将构造树的问题转化为构造序列,将统计树的问题转化为统计序列,将树的dp转化为序列的dp。如何得到prufer序列?统计树上的所有节点的度数\(d_i\)。找到所有度数为\(1\)的节点......
  • R语言k-Shape时间序列聚类方法对股票价格时间序列聚类|附代码数据
    原文链接:http://tecdat.cn/?p=3726最近我们被客户要求撰写关于时间序列聚类的研究报告,包括一些图形和统计输出。本文我们将使用k-Shape时间序列聚类方法检查与我们有业务关系的公司的股票收益率的时间序列企业对企业交易和股票价格在本研究中,我们将研究具有交易关系的公司的......
  • 资源加载和序列化
    一切加载最后都要跑到LoadPackageInternal:创建Linker序列化(LoadAllObjects){ FUObjectSerializeContext*InOutLoadContext=LoadContext; Linker=GetPackageLinker(InOuter,PackagePath,LoadFlags,nullptr,InReaderOverride,&InOutLoadContext,ImportLinker,In......
  • 2024年公共管理、心理健康与教育国际学术会议
    2024年应用经济学与财务管理国际学术会议(PMMHE2024)2024InternationalAcademicConferenceonPublicManagement,MentalHealth,andEducation【会议简介】 2024年公共管理、心理健康与教育国际学术会议将于美丽的杭州隆重召开。本次会议旨在汇聚全球公共管理、心理......
  • abc253E 相邻元素之差不低于K的序列数
    给定n,m,k,找一个序列A[n],使用满足1<=A[i]<=m,并且任意相邻两元素的差的绝对值大于等于k,求满足条件的序列个数,求998244353取模。2<=n<=1000;1<=m<=5000;0<=k<=m-1设dp[i][j]表示前i个数,以j结尾的方案数,在计算dp[i+1][k]时,可以枚举j进行统计,复杂度为O(n^3),可以通过前缀和优化成O(......
  • python时间序列缺失值补零
    有个雨滴谱的数据,情况是有雨滴的时候会记录那个时刻的雨滴情况,但是无雨滴的时间没有记录那么我想花一个雨滴时间序列的情况,就需要补全没有雨滴的时间,并且记录为0数据情况如下: python代码:#!usr/bin/envpython#-*-coding:utf-8-*-"""@author:Su@file:timecomplet.p......