首页 > 代码库 > LCIS(最长公共上升子序列)Vijos1264神秘的咒语

LCIS(最长公共上升子序列)Vijos1264神秘的咒语

描述

身为拜月教的高级间谍,你的任务总是逼迫你出生入死。比如这一次,拜月教主就派你跟踪赵灵儿一行,潜入试炼窟底。

据说试炼窟底藏着五行法术的最高法术:风神,雷神,雪妖,火神,山神的咒语。为了习得这些法术,要付出艰辛的努力,但是回报同样十分丰厚。

拜月希望你告诉他咒语的长度为多少。(你:“请问您想知道咒语的具体内容吗?”拜月:“想,但是vijos不支持special judge。”-_-原来大人物也有大人物的悲哀。。。)
于是你偷偷躲在一边,想乘机看看咒语究竟是什么。突然,天空(??试炼窟底看的到天空??)出现了两条非常长的数字串,你抓狂了。究竟哪个才是真正的咒语呢?你突然想到,这两个都不是咒语(不妨称之为伪咒语),而真正的咒语却与他们有着密切的联系。于是你打开拜月亲手给你写的纸条:"The Real Incantation is Their Common Increasing Subsequence of Maximal Possible Length"
"该死的拜月,居然还会E文!"你咒骂着,但为了一家老小的生命,又不得不卖命地算着咒语的长度。

格式

输入格式

第一行为1个数N,代表有N组测试数据。

对于每组测试数据,描述了两条数字串,首先一个数字为一条伪咒语的长度M,接下来M个数描述了伪咒语的内容。

输出格式

共N行,每行一个数字,描叙了对应咒语的长度。

样例1

样例输入1[复制]

15 1 4 2 5 -124 -12 1 2 4

样例输出1[复制]

2

限制

1s

提示

对于100%的数据,有1<=N<=5,1<=M<=500,Ai,Bi在长整型范围内。

--------------------------------------

f[i][j]表示a的前i个以b[j]结尾的lcis

a[i]!=b[j], f[i][j]=f[i-1][j]

a[i]==b[j], f[i][j]=max{f[i-1][k]}1<=k<=j-1&&b[k]<b[j]

这样O(n3)

优化:如何快速找到max{f[i-1][k]}?

外层i内层j

如果a[i]>b[j],显然可以用f[i-1][j]的值来更新f[i][?]的值(b[?]==a[i])

在外层维护一个mx就可以了

当然可以滚掉第一维,还省去了f[i-1][j]这个转移

 

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int M=505;int n,la,lb,a[M],b[M],ans=0;int f[M];void dp(){    int mx=0;    for(int i=1;i<=la;i++){        mx=0;        for(int j=1;j<=lb;j++){            if(a[i]>b[j]) mx=max(mx,f[j]);            if(a[i]==b[j]) f[j]=mx+1;        }    }}int main(int argc, const char * argv[]) {    scanf("%d",&n);    for(int i=1;i<=n;i++){        memset(f,0,sizeof(f));ans=0;        scanf("%d",&la);        for(int i=1;i<=la;i++) scanf("%d",&a[i]);        scanf("%d",&lb);        for(int i=1;i<=lb;i++) scanf("%d",&b[i]);        dp();        for(int i=1;i<=lb;i++) ans=max(ans,f[i]);        printf("%d\n",ans);    }    return 0;}

 

LCIS(最长公共上升子序列)Vijos1264神秘的咒语