题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1264

题意:给出两个数列,每个数列的长度为5n,其中1-n每个数字各出现5次。求两个数列的最长公共子列。

思路:LCS转变为LIS,对于每个在第一个数组中出现的数字,将它转变为在第二个数组里出现的位置,注意这个位置要从大到小排,然后对这个数组做LIS。

#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
int q[],a[],b[],n,p[],s[][];
int find(int x){
int l=,r=q[],ans;
if (x<=q[]) return ;
while (l<=r){
int mid=(l+r)/;
if (q[mid]<x) ans=mid,l=mid+;
else r=mid-;
}
if (q[ans+]<x) return ans+;
return ans;
}
int main(){
scanf("%d",&n);
for (int i=;i<=*n;i++) scanf("%d",&a[i]);
for (int j=;j<=*n;j++) scanf("%d",&b[j]);
for (int i=;i<=*n;i++){
for (int j=;j<=;j++)
if (s[b[i]][j]==){
s[b[i]][j]=i;
break;
}
}
for (int i=;i<=*n;i++){
int t=a[i];
for (int j=;j>=;j--) p[++p[]]=s[t][j];
}
q[]=;
q[]=p[];
for (int i=;i<=p[];i++){
if (p[i]>q[q[]]) q[++q[]]=p[i];
else{
int t=find(p[i]);
q[t+]=p[i];
}
}
printf("%d\n",q[]);
}

最新文章

  1. PHP json_encode / json_decode
  2. (笔记)Linux内核学习(十一)之I/O层和I/O调度机制
  3. ios-消息弹框之UIAlertView, UIActionSheet以及UIAlertController小结
  4. 压力测试的轻量级具体做法 Apache ab
  5. applicationContext.xml详解 spring+mybatis+struts
  6. hdu-5009-Paint Pearls-dp
  7. C和指针c6-1
  8. 使用Identity Server 4建立Authorization Server (3)
  9. P2255 [USACO14JAN]记录奥林比克
  10. 浅谈构建前端自动化工作流程一 之 node
  11. 容器中的诊断与分析4——live diagnosis——LTTng
  12. shell编程之转义和引用
  13. 如何使用List&lt;HashMap&lt;String, String&gt;&gt;详细讲解
  14. msp430板子接485接口的气体传感器问题及处理
  15. 非系统服务如何随系统启动时自动启动(rc.local加了可执行权限,仍然没有生效)
  16. Java实现打印功能
  17. 1. Apache Axis2 下载安装入门
  18. linux strace 命令详解
  19. 使用VisualSVN Server搭建SVN服务器[xyytit]
  20. Android网络缓存的实现思路

热门文章

  1. 根据SVN的MESSAGE进行多版本输出,反向排序,真是曲折~~~啊
  2. Codeforces 335B Palindrome
  3. IC卡接口芯片TDA8007的读写器设计
  4. QDialog 模态对话框与事件循环(exec其实就是调用了show和eventLoop.exec)
  5. Powershell 定义文本
  6. 2015必须推荐的Android框架,猿必读系列!
  7. translate函数说明
  8. Android 读取手机SD卡根目录下某个txt文件的文件内容
  9. MVC MVC 路由详解
  10. qt动态更新界面的菜鸟代码,请指出