CodeForces 10D. LCIS 最长公共上升子序列模板题 + 打印路径

CodeForces 10D. LCIS 最长公共上升子序列模板题 + 打印路径

大家好,又见面了,我是全栈君。

推荐一篇炒鸡赞的blog。

以下代码中有打印路径。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <ctime>
#include <iomanip>

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-6)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 1000000007

using namespace std;

int A[510],B[510];

int py[510][510],px[510][510],dp[510][510] = {0};

void Output(int x,int y)
{
    if(x == -1 && y == -1)
        return ;

    Output(px[x][y],py[x][y]);

    if(A[x] == B[y])
        printf("%d ",A[x]);
}

int main()
{
    int n,m,i,j,mlen,x,y;

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

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

    int Max = 0,ax,ay;

    for(i = 1;i <= n; ++i)
    {
        mlen = 0,x = -1,y = -1;
        for(j = 1;j <= m; ++j)
        {
            dp[i][j] = dp[i-1][j];
            px[i][j] = i-1,py[i][j] = j;
            if(B[j] < A[i] && dp[i-1][j] > mlen)
                mlen = dp[i-1][j],x = i-1,y = j;

            if(B[j] == A[i])
                dp[i][j] = mlen + 1,px[i][j] = x,py[i][j] = y;
            if(dp[i][j] > Max)
                Max = dp[i][j],ax = i,ay = j;
        }
    }

    if(Max)
        printf("%d\n",Max),Output(ax,ay);
    else
        printf("0\n");
    return 0;
}

















版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115817.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • sql prompt插件的安装

    sql prompt插件的安装这里写自定义目录标题UnabletoconnecttotheRedgateClientService解决方法新手小白,记录一下第一次安装MicrosoftSQLServerManagementStudio(以下简称为ssms),以及它的插件sqlprompt遇到的问题。UnabletoconnecttotheRedgateClientService首先,成功安装了ssms,然后下载了sqlprompt插件的安装包。可以去它的官网下载,懒得找的话我也帮忙找到了它的

  • 史上最简单的 SpringCloud 教程 | 第一篇: 服务的注册与发现Eureka(Finchley版本)

    史上最简单的 SpringCloud 教程 | 第一篇: 服务的注册与发现Eureka(Finchley版本)转载请标明出处:http://blog.csdn.net/forezp/article/details/69696915本文出自方志朋的博客一、springcloud简介鉴于《史上最简单的SpringCloud教程》很受读者欢迎,再次我特意升级了一下版本,目前支持的版本为SpringBoot版本2.0.3.RELEASE,SpringCloud版本为F…

  • [图文教程] 手把手教你安装Android SDK

    [图文教程] 手把手教你安装Android SDK配置环境总是痛苦的,不断地找教程,寻方法……在不断犯错的道路上跌跌撞撞……有点收获还好但是!几百年不配置一次环境,要这经验值何用?记录下来吧,以后也可以傻瓜式跟着教程走我已经下载并安装了AndroidStudio没有下载安装的可移步————>AndroidStudio官网下载开始下载AndroidSDK不用跑了——》AndroidSDK免费下载安装地址不让改不是…下一步吧安装权限……好像问题不大,下一步安装位置……可以更改…

  • vscode设置字体大小和字体_vscode snippet

    vscode设置字体大小和字体_vscode snippetvscode设置字体vscode设置字体查看vscode当前的字体github搜索自己喜欢的字体设置vscode字体配置vscode设置字体安装下载完成后总感觉字体不好看,想换别的字体,怎么办,只需要如下几步即可搞定查看vscode当前的字体****如上图,我得vscode字体是已经设置过的,vscode默认字体是Consolas格式的,我个人不太喜欢,所以就从网上下载别的字体。github搜索自己喜欢的字体比如我下载的就是Hack字体,github上直接搜索Hack字体是直接可以下载安装

  • python deepcopy_python中的深拷贝(deepcopy)和浅拷贝(copy)介绍及代码参考「建议收藏」

    python deepcopy_python中的深拷贝(deepcopy)和浅拷贝(copy)介绍及代码参考「建议收藏」在python中,对象赋值实际上是对象的引用。当创建一个对象,然后把它赋给另一个变量的时候,python并没有拷贝这个对象,而只是拷贝了这个对象的引用。以下分两个思路来分别理解浅拷贝和深拷贝:(1)利用切片操作和工厂方法list方法拷贝(2)利用copy中的deepcopy方法进行拷贝1、利用切片操作和工厂方法list方法拷贝代码场景:有一个小伙jack,tom通过切片操作拷贝jack,anny通…

  • 【跃迁之路】【502天】刻意练习系列261(2018.06.22)

    【跃迁之路】【502天】刻意练习系列261(2018.06.22)

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号