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