描述
身为拜月教的高级间谍，你的任务总是逼迫你出生入死。比如这一次，拜月教主就派你跟踪赵灵儿一行，潜入试炼窟底。
据说试炼窟底藏着五行法术的最高法术：风神，雷神，雪妖，火神，山神的咒语。为了习得这些法术，要付出艰辛的努力，但是回报同样十分丰厚。
拜月希望你告诉他咒语的长度为多少。（你：“请问您想知道咒语的具体内容吗？”拜月：“想，但是vijos不支持special judge。”-_-原来大人物也有大人物的悲哀。。。）
于是你偷偷躲在一边，想乘机看看咒语究竟是什么。突然，天空（？？试炼窟底看的到天空？？）出现了两条非常长的数字串，你抓狂了。究竟哪个才是真正的咒语呢？你突然想到，这两个都不是咒语（不妨称之为伪咒语），而真正的咒语却与他们有着密切的联系。于是你打开拜月亲手给你写的纸条："The Real Incantation is Their Common Increasing Subsequence of Maximal Possible Length"
"该死的拜月，居然还会E文!"你咒骂着，但为了一家老小的生命，又不得不卖命地算着咒语的长度。
格式
输入格式
第一行为1个数N,代表有N组测试数据。
对于每组测试数据，描述了两条数字串，首先一个数字为一条伪咒语的长度M，接下来M个数描述了伪咒语的内容。
输出格式
共N行，每行一个数字，描叙了对应咒语的长度。
限制
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 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=;
int n,la,lb,a[M],b[M],ans=;
int f[M];
void dp(){
int mx=;
for(int i=;i<=la;i++){
mx=;
for(int j=;j<=lb;j++){
if(a[i]>b[j]) mx=max(mx,f[j]);
if(a[i]==b[j]) f[j]=mx+;
}
}
}
int main(int argc, const char * argv[]) {
scanf("%d",&n);
for(int i=;i<=n;i++){
memset(f,,sizeof(f));ans=;
scanf("%d",&la);
for(int i=;i<=la;i++) scanf("%d",&a[i]);
scanf("%d",&lb);
for(int i=;i<=lb;i++) scanf("%d",&b[i]);
dp();
for(int i=;i<=lb;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
}
return ;
}