$Description$
求两个序列的最长公共上升子序列
$Solution$
$f[i][j]$表示$a$序列匹配到$i$和$b$序列匹配到$j$的最长上升序列的长度,这里并不要求$a[i]==b[j]$。
两层循环,外层$i=1...n1$,内层$j=1...n2$
转移:
$f[i][j]=max(f[i-1][1...j-1](if\ b[j]<a[i]))+1$
这里的$max(f[i-1][i...j-1](if\ b[j]<a[i]))$不用每次单独枚举,只要在循环内即使更新就可以了
或者,也可以用树状数组来维护.
$Code$
#include<bits/stdc++.h>
#define Ri register int
#define il inline
#define go(i,a,b) for(Ri i=a;i<=b;++i)
#define yes(i,a,b) for(Ri i=a;i>=b;--i)
#define e(i,u) for(Ri i=b[u];i;i=a[i].nt)
#define ll long long
#define db double
using namespace std;
il int read()
{
Ri x=,y=;char c=getchar();
while(c<'' || c>''){if(c=='-')y=-;c=getchar();}
while(c>='' && c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}
return x*y;
}
const int N=;
int n,m,a[N],b[N],f[N][N],as,d[N],t[N][N*];
struct nd{int d,p;}c[N];
il bool cmp(nd x,nd y){return x.d<y.d;}
il int lowbit(Ri x){return x&(-x);}
il void change(Ri i,Ri j,Ri dat)
{
while(i<=n)
{
t[j][i]=max(t[j][i],dat);
i+=lowbit(i);
}
}
il int sum(Ri i,Ri j)
{
Ri ret=;
while(i>)
{
ret=max(ret,t[j][i]);
i-=lowbit(i);
}
return ret;
}
int main()
{
freopen("lcis.in","r",stdin);
freopen("lcis.out","w",stdout);
n=read(),m=read();
go(i,,n)a[i]=read(),c[i]=(nd){a[i],i};
go(i,,m)b[i]=read();
sort(c+,c+n+,cmp);
go(i,,n)
if(i>= && c[i].d==c[i-].d)d[c[i].p]=d[c[i-].p];
else d[c[i].p]=i;
go(i,,n)
{
go(j,,m)
{
f[i][j]=max(f[i][j],f[i][j-]);
if(a[i]==b[j])
f[i][j]=max(f[i][j],sum(d[i]-,j-)+);
}
go(j,,m)change(d[i],j,f[i][j]);
}
go(i,,n)as=max(as,f[i][m]);
printf("%d\n",as);
return ;
}
View 树状数组 Code
#include<iostream>
#include<cstdio>
#include<cstring>
#define Rg register
#define il inline
#define db double
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a));
#define go(i,a,b) for(Rg int i=a;i<=b;i++)
#define yes(i,a,b) for(Rg int i=a;i>=b;i--)
using namespace std;
il int read()
{
int x=,y=;char c=getchar();
while(c<''||c>''){if(c=='-')y=-;c=getchar();}
while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}
return x*y;
}
const int N=;
int T,n1,n2,ans,a[N],b[N],al[N],f[N][N],lst[N][N];
il void sol()
{
ans=;mem(f,);int x=n1,y=,t;
go(i,,n1)
{
t=;
go(j,,n2)
{
if(a[i]!=b[j])f[i][j]=f[i-][j];
if(a[i]>b[j]&&f[i][j]>f[i][t])t=j;
if(a[i]==b[j])f[i][j]=f[i][t]+,lst[i][j]=t;
//cout<<"f["<<i<<"]["<<j<<"]:"<<f[i][j]<<endl;
}
}
go(i,,n2)if(f[n1][i]>ans)ans=f[n1][i],y=i;
t=;
while(f[x][y])
{
while(a[x]!=b[y]){x--;if(!x)return;}
al[ans-t]=b[y],y=lst[x][y],t++;
}
}
int main()
{
T=read();
while(T--)
{
n1=read();go(i,,n1)a[i]=read();
n2=read();go(i,,n2)b[i]=read();
sol();
printf("%d\n",ans);
if(ans){go(i,,ans)printf("%d ",al[i]);printf("\n");}
}
return ;
}
随机推荐
-
解决使用Skia图形库时遇到的几个问题
Skia是一个开源的2D图形库,提供通用的API,适用于工作中遇到的各种硬件和软件平台.这是谷歌浏览器Chrome OS,Android的图形引擎,Mozilla Firefox浏览器和Firefox ...
-
Linux screen命令简介
Linux上有的shell脚本运行时候是阻塞的,如果想在屏幕上即能够看到阻塞命令的输出,同时又能够在shell窗口运行其他程序,那么Linux自带的screen命令是非常不错的选择. 1.screen ...
-
__name__ == &#39;__main__&#39;的作用
当你打开一个.py文件时,经常会在代码的最下面看到if __name__ == '__main__':,现在就来介 绍一下它的作用. 模块是对象,并且所有的模块都有一个内置属性 __name__.一个 ...
-
Cocos2d-x 3.2 大富翁游戏项目开发-第八部分 角色的散步路径
获得所述路径之后.我们将能够使根据的步行路径的作用,当您点击gobutton什么时候.我们呼吁player的startGo()办法.传入的参数是保存路径2一维数组 void GameBaseScene ...
-
Raphael的transform用法
Raphael的transform用法 <%@ page language="java" contentType="text/html; charset=UTF-8 ...
-
oracle11g中SQL优化(SQL TUNING)新特性之SQL Plan Management(SPM)
1. 简介 Oracle Database11gR1引进了SQL PlanManagement(简称SPM),一套允许DBA捕获和保持任意SQL语句执行计划最优的新工具,这样,限制了刷新优化器统计 ...
-
计算机网络相关:应用层协议(一):DNS
DNS 1.概念 DNS是: 1) 一个有分层的DNS服务器实现的分布式数据库 2)一个使得主机能够查询分布式数据库的应用协议. 它运行在UDP之上,默认使用53号端口. 主要功能 是将主 ...
-
mysql中using
select * from ( SELECT u.utm_source ,count(DISTINCT u.mobile) as new_user -- 登记用户 FROM 表名 u WHERE u. ...
-
关于jsonp跨域的 实现
1.实现原理 1.把接口写在 script标签的src 中 这个接口就可以访问(不会存在跨域问题 因为接口在浏览器地址栏是可以访问的 会返回json字符串); 2.直接写不可以 因为正常情 ...
-
Android下文件的压缩和解压(Zip格式)
Zip文件结构 ZIP文件结构如下图所示, File Entry表示一个文件实体,一个压缩文件中有多个文件实体. 文件实体由一个头部和文件数据组,Central Directory由多个File he ...