#10 D. LCIS （dp+最长公共上升子序列）

偏执的太偏执、 2022-06-15 22:49 153阅读 0赞

题目链接：

[点击打开链接][Link 1]

http://codeforces.com/contest/10/problem/D

题意：

求最长公共上升子序列。

题解：

假设dp\[ i \]表示第二个串位置为 i 的时候与第一个串的的最长公共上升子序列是多少。

枚举第一个串，再枚举第二个串。

for(int i = 1; i<=n ; i++)

\{

int pos=0;

for(int j=1; j<=m;j++)

\{

if(a\[i\]==b\[j\])

\{

dp\[j\]=dp\[pos\]+1;

\}

else if (a\[i\] > b\[j\] && dp\[j\]>dp\[pos\])

\{

pos=j;

\}

\}

\}

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    int dp[567],a[567],b[567],step[567];
    int n,m;
    void print(int x)
    {
    	if(x==0)return;
    	print(step[x]);
    	printf("%d ",b[x]);
    }
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    	}
    	cin>>m;
    	for(int j=1;j<=m;j++){
    		cin>>b[j];
    	}
    	
    	for(int i=1;i<=n;i++)
    	{
    		int pos=0;
    		for(int j=1;j<=m;j++)
    		{
    			if(a[i]==b[j])
    			{
    				dp[j]=dp[pos]+1;
    				step[j]=pos;
    			}
    			else if(a[i] > b[j] && dp[j] > dp[pos])
    			{
    				pos=j;
    			}
    		}
    	}
    //	for(int i=1;i<=m;i++)cout<<dp[i]<<" ";cout<<endl;
    	int x=0;
    	int ans=0;
    	for(int i=1;i<=m;i++)
    	{
    		if(dp[i]>ans)
    		{
    			ans=dp[i];
    			x=i;
    		}
    	}
    	cout<<ans<<endl;
    	print(x);
    	return 0;
    }

[Link 1]: http://codeforces.com/contest/10/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，153人围观）

还没有评论，来说两句吧...

相关阅读

相关最长公共子序列（LCS）与最长公共子串(DP)

《1》[最长公共子序列（LCS）与最长公共子串(DP)][LCS_DP] http://blog.csdn.net/u012102306/article/details/53

亦凉/ 2024年02月19日 13:24/ 0 赞/ 16 阅读

相关 Alignment （DP基础--最长上升子序列）

目录 Alignment （DP基础--最长上升子序列）题目题意思路代码 Alignmen

迷南。/ 2023年06月01日 06:11/ 0 赞/ 7 阅读

相关 272 最长公共上升子序列

1. 问题描述：熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。小沐沐

朱雀/ 2022年09月12日 01:54/ 0 赞/ 171 阅读

相关 dpPOJ 2027 LCIS（最长上升公共子序列）

题意和解析见代码最后部分 include<iostream> include <cstdio> include <cstring>

我不是女神ヾ/ 2022年08月18日 00:48/ 0 赞/ 140 阅读

相关病毒（LICS 最长上升公共子序列）

你有一个日志文件，里面记录着各种系统事件的详细信息。自然的，事件的时间戳按照严格递增顺序排列（不会有两个事件在完全相同的时刻发生）。遗憾的是，你的系统被病毒感染了，日志文件

拼搏现实的明天。/ 2022年07月03日 14:29/ 0 赞/ 154 阅读

相关 #10 D. LCIS （dp+最长公共上升子序列）

题目链接： [点击打开链接][Link 1] http://codeforces.com/contest/10/problem/D 题意：求最长公共上升子

偏执的太偏执、/ 2022年06月15日 22:49/ 0 赞/ 154 阅读

相关最长公共子序列(DP)

给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB 则这两个字符串

た入场券/ 2022年06月10日 11:41/ 0 赞/ 161 阅读

相关最长上升子序列（DP）

问题描述一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列

落日映苍穹つ/ 2022年06月10日 10:36/ 0 赞/ 272 阅读

相关 zoj2432 hdoj1423 最长公共上升子序列（LCIS）

zoj2431 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2432 hdoj 1423 htt

深藏阁楼爱情的钟/ 2022年01月10日 05:41/ 0 赞/ 168 阅读

相关 CH5101 LCIS（最长公共上升子序列）

题意：求两个序列的最长公共上升子序列。分析：《算法竞赛进阶指南》P266。代码： include <cstdio> include <iostream

淩亂°似流年/ 2021年11月26日 13:58/ 0 赞/ 239 阅读