LCIS(最长公共上升子序列)模板
2024-09-06 18:25:31
求出LCIS并输出其路径。
1 #include <iostream>
2 #include <cstdio>
3 #include <string>
4 #include <cstring>
5 #include <fstream>
6 #include <algorithm>
7 #include <cmath>
8 #include <queue>
9 #include <stack>
10 #include <vector>
11 #include <map>
12 #include <set>
13 #include <iomanip>
14 using namespace std;
15 typedef long long ll;
16 const int maxn = 511;
17 int nua[maxn];
18 int nub[maxn];
19 int dp[maxn];
20 int pre[maxn];
21 void print(int x)
22 {
23 if(x==0) return;
24 print(pre[x]);
25 cout<<nub[x]<<" ";
26 }
27 int main()
28 {
29 ios::sync_with_stdio(false);
30 int n,m;
31 cin>>n;
32 for(int i=1;i<=n;++i)
33 cin>>nua[i];
34 cin>>m;
35 for(int i=1;i<=m;++i)
36 cin>>nub[i];
37 for(int i=1;i<=n;++i)
38 {
39 int pos=0;
40 for(int j=1;j<=m;++j)
41 {
42 if(nua[i]==nub[j])
43 {
44 dp[j]=dp[pos]+1;
45 pre[j]=pos;
46 }
47 if(nua[i]>nub[j] && dp[pos]<dp[j]) {
48 pos=j;
49 }
50 }
51 }
52 int ansa=0,ansb=0;
53 for(int i=1;i<=m;++i)
54 {
55 if(dp[i]>ansb)
56 {
57 ansb=dp[i];
58 ansa=i;
59 }
60 }
61 cout<<ansb<<endl;
62 print(ansa);
63 return 0;
64 }
最新文章
- alpha值的问题
- git 创建版本库
- [Java拾遗一] XML的书写规范与解析.
- iOS从App跳转至系统设置菜单各功能项的编写方法讲解
- iso中自动伸缩属性
- [Express] Level 2: Middleware -- 1
- winform Chart控件 获取鼠标处坐标值方法
- out ref区别
- windows升级到1607后操作很卡顿的解决办法
- 深入理解css中vertical-align属性
- Centos7安装Tair及配置测试
- js创建对象,放进js集合
- 【工具相关】Web-Sublime Text2-通过Package Control安装插件
- python基本数据类型 数字 和 字符串
- No module named &#39;pandas._libs.tslib&#39;
- Reg 命令修改注册表
- ORM跨表查询问题
- 20172308 实验一《Java开发环境的熟悉》实验报告
- diamond types are not supported at this language level
- 字王4K云字库入驻github