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

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

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

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

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

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

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

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

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

 输入样例

1
5 1 4 2 5 -12
4 -12 1 2 4

输出样例

2 

思路 

这是一个最长上升公共子序列的问题，用dp的方法来做；

首先定义一个状态dp[i][j]，表示以a串的前i个整数与b串的前j个整数且以b[j]为结尾构成的LCIS的长度。

接下来枚举两个字符串，用一个二重循环，外层为i，内层为j，有两种情况

1、当a[i] == b[j] 的时候，那么状态转移方程就是 

                                dp[i][j] = max(dp[i][j], dp[i-1][k] + 1);

1 <= k < j 并且 b[j] > b[k] (要满足这是个上升子序列)

2、当a[i] != b[j] 的时候，

                                dp[i][j] = dp[i - 1][j];

因为a[i] 和 b[j] 不相等，所以最大上升子序列肯定不会增加，a串的前i- 1个整数与a串的前i个整数在b串的前j个整数且以b[j]为结尾构成的LCIS是肯定相等的

 代码

#include<iostream>
#include<algorithm>
#include<string.h>
int a[510],b[510];
int dp[510][510]; //表示以a串的前i个整数与b串的前j个整数且以b[j]为结尾构成的LCIS的长度。
using namespace std;
int main(){int t;scanf("%d",&t);int n,m;while(t--){memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(dp,0,sizeof(dp));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d",&b[i]);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i] != b[j]){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = 1;for(int k=1;k<j;k++){if(b[j] > b[k]) dp[i][j] = max(dp[i][j], dp[i-1][k] + 1);}}}}int res = 0;for(int i=1;i<=m;i++){res = max(res, dp[n][i]);}printf("%dn",res);}return 0;
}

优化

可以把dp优化成一维的，并且当存下之前的LCIS长度，这样就可以不用遍历k了