首页 > 其他分享 >LIS LCS LCIS

LIS LCS LCIS

时间:2023-08-15 17:34:43浏览次数:30  
标签:arr LCIS LCS int maxn ini LIS include dp


//LIS 最长上升子序列 o(n^2)
/*
arr[k]>arr[i]&&dp[k]<dp[i]+1

1 3 4 2 5
  2 2 2 2
    3 2 3
      2 4
*/

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=1000+10;
int arr[maxn],dp[maxn]; //dp[] 用来储存最优解
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int ans=0;
        for(int i=0;i<n;i++)
            scanf("%d",&arr[i]);
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=0;i<n;i++)
        {
            for(int k=i+1;k<n;k++)
            {
                if(arr[k]>arr[i]&&dp[k]<dp[i]+1)
                    dp[k]=dp[i]+1;
            }
            ans=max(ans,dp[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}



//o(nlogN)
/*
1 3 4 2 5
1 2 3 2 4
*/

#include <stdio.h>
#include <string.h>

const int maxn=100000+10;
int arr[maxn],dp[maxn]; //dp[i] 最长上升子序列个数为i的所有子串结尾的最小值

int Search(int se_num,int right)
{
    int middle,left=1;
    while(left<=right)
    {
        middle=(left+right)/2;
        if(dp[middle]<se_num)
            left=middle+1;
        else
            right=middle-1;
    }
    return left;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int ini=1;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%d",&arr[i]);
        dp[ini]=arr[1];
        for(int i=2;i<=n;i++)
        {
            if(arr[i]>dp[ini])
                dp[++ini]=arr[i];
            else
            {
                int pos=Search(arr[i],ini);
                dp[pos]=arr[i];
            }
        }
        printf("%d\n",ini);
    }
    return 0;
}



//LCS o(n*m)
//用矩阵的方法将n,m作为行和列,有相同元素时为1不同时为0
//最长的公共子序列 每次记录时加上对角线上的值
/*
i==0,j==0 dp[i][j]=0;
i,j>0 a[i]==b[j] dp[i][j]=dp[i-1][j-1]+1;
i,j>0 a[i]!=b[j] dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
*/

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int maxn=1000+10;
int a[maxn],b[maxn],dp[maxn][maxn]; //dp 记录最优解

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int k=1;k<=m;k++)
            scanf("%d",&b[k]);
        for(int i=1;i<=n;i++)
        {
            for(int k=1;k<=m;k++)
            {
                if(a[i]==b[k])  //字符串时改成a[i-1]==b[i-1]即可
                    dp[i][k]=dp[i-1][k-1]+1;
                else
                    dp[i][k]=max(dp[i-1][k],dp[i][k-1]);
            }
        }
        printf("%d\n",dp[n][m]);
    }

    return 0;
}




//LCIS o(n*m)
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int maxn=1000+10;
int a[maxn],b[maxn],dp[maxn];  //dp 记录以b[i]结尾的最优解

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int k=0;k<m;k++)
            scanf("%d",&b[k]);
        for(int i=0;i<n;i++)
        {
            int MAX=0;
            for(int k=0;k<m;k++)
            {
                if(a[i]>b[k]&&MAX<dp[k]) //当a[i]==b[k]时 查找从1到k-1中的最优解
                    MAX=dp[k];
                if(a[i]==b[k])
                    dp[k]=MAX+1;
            }
        }
        int ans=0;
        for(int i=0;i<m;i++)
            if(ans<dp[i])
                ans=dp[i];
        printf("%d\n",ans);
    }
    return 0;
}




标签:arr,LCIS,LCS,int,maxn,ini,LIS,include,dp
From: https://blog.51cto.com/u_3936220/7091410

相关文章

  • HDU 1087 (LIS)
    SuperJumping!Jumping!Jumping!TimeLimit:2000/1000MS(Java/Others)  MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):28091  AcceptedSubmission(s):12529ProblemDescriptionNowadays,akindofchessgamecalled“SuperJumping!Jump......
  • 通过 Listener 解决 Slider 滑动冲突
    问题背景 在Flutter中,我们经常使用ScrollView+Slider这样的场景。但是在这样的场景下,存在用户体验并不好的问题:列表滑动的过程中Slider不能响应举例:1\.滑动未完成,Slider不能响应SingleChildScrollView在我们手指抬起的过程中,还是会有一定的惯性,列表不会立刻停止。它这......
  • CMakeLists语法详解
     https://www.jianshu.com/p/eb25baf5ca19set(Root"${CMAKE_CURRENT_SOURCE_DIR}")set(Base64${Root}/lib/libb64/src)include_directories(${OpenCV_INCLUDE_DIRS})include_directories(${Root})include_directories(${Root}/lib/libb64/include) include_dir......
  • Profession English
    runoutofsomething -touseallofsomething-tohavenothingleft.e.g. Theprinterhasrunoutofink.Canyouchangethecartridgeplease?Weonlyhaveacoupleofweekstofinishtheproject-we'rerunningoutoftime! figuresomethingout -......
  • 已知两个128维向量,向量格式为list,计算两个向量的余弦相似性
    计算两个向量的余弦相似度可以使用以下公式:余弦相似度=(向量A·向量B)/(||向量A||*||向量B||)其中,向量A·向量B表示向量A和向量B的点积(内积),||向量A||和||向量B||表示向量A和向量B的欧几里德范数(模)。下面是一个示例代码,展示如何计算两个128维向量的余弦相似度:imp......
  • Oracle启动监听报错:The listener supports no services或出现 unknown状态解决
    1、查看$ORACLE_HOME/network/admin/listener.ora文件中的host是否正确,能不能ping通2、查看$ORACLE_HOME/network/admin/tnsnames.ora文件中的host是否与listener.ora中的一致3、查看/etc/hosts文件中的127.0.0.1是不是localhost,listener.ora中host跟这里的是否一样4、登录数......
  • Leetcode 206. 反转链表(Reverse linked list)
    题目链接给你单链表的头节点head,请你反转链表,并返回反转后的链表。示例1:输入:head=[1,2,3,4,5]输出:[5,4,3,2,1]示例2:输入:head=[1,2]输出:[2,1]提示:链表中节点的数目范围是[0,5000]-5000<=Node.val<=5000思路迭代法:创建两个指针,分别指向当前节......
  • 废柴英语在中文中通常翻译为"useless English"或"rubbish English"
    废柴英语怎么说提问者:u627050 最后回答时间:2023-01-31废柴英语在中文中通常翻译为"uselessEnglish"或"rubbishEnglish"。它指的是不流利或不准确的英语表达。这个词的来源可能源于把英语作为一种废物或无用之物的看法。下面是一些英文例句及其中文翻译:"MyEnglishisreallyba......
  • English考研名师
    考研名师墨东博考研教育网辅导教师墨东博,男,著名考研辅导专家,原新东方考研体系设计者,英语应试辅导名师。中文名墨东博性    别男主    修产业经济学现    任考研教育网考研英语核心主讲其在国内学习英美文学,后去美国宾夕法尼亚大学留学,主修产业经济学。墨东博是北京......
  • "Don't be shy. Speak English loudly and crazily!"
    "Don'tbeshy.SpeakEnglishloudlyandcrazily!" 俞敏洪犀利点评马云、王石、刘强东、雷军英语水平俞敏洪:马云8岁学英语,考上杭师范读专科,而我在北大读本科! 李阳、马云、俞敏洪,这三个中国最著名的英语老师,只有李阳仍坚守在一线。是啊,当马云再次登上福布斯中国富豪榜......