hdu 1423 Greatest Common Increasing Subsequence（最长公共递增子序列lcis）

http://acm.hdu.edu.cn/showproblem.php?pid=1423

Problem Description

This is a problem from ZOJ 2432.To make it easyer,you just need output the length of the subsequence.

Input

Each sequence is described with M - its length (1 <= M <= 500) and M integer numbers Ai (-2^31 <= Ai < 2^31) - the sequence itself.

Output

output print L - the length of the greatest common increasing subsequence of both sequences.

Sample Input

1 4 2 5 -12

-12 1 2 4

Sample Output

lcis：dp

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<math.h>
 4 #include<algorithm>
 5 #include<string.h>
 6 #include<string>
 7 #include<ctime>
 8 #include<queue>
 9 #include<list>
10 #include<map>
11 #define INF 9999999
12 #define MAXN 10000
13 using namespace std;
14 //    priority_queue<int,vector<int>,greater<int> > pq;
15 
16 int dp[550];//b数组到第j个数字时，该数字位置处的公共递增因子数
17 
18 int main()
19 {
20     int t;
21     cin>>t;
22     while(t--)
23     {
24         int n,m;
25         cin>>n;
26         int i,j,a[550],b[550];
27         for(i=0;i<n;i++)
28             cin>>a[i];
29         cin>>m;
30         for(i=0;i<m;i++)
31             cin>>b[i];
32         memset(dp,0,sizeof(dp));
33     //    dp[0]=-1;
34         for(i=0;i<n;i++)
35         {
36             int k=0;
37             for(j=0;j<m;j++)
38             {
39                 //当前要比较的数值为a[i],所以我们寻找b[j]中比a[i]小，但dp[j]最大的值,找到了就用k记录位置 
40                 if(a[i]>b[j]&&dp[j]>dp[k])
41                     k=j;
42                 if(a[i]==b[j])
43                     dp[j]=dp[k]+1;  //dp[k]值+1就为当前字符的公共递增因子数
44             }
45         }
46         int maks=-1;
47         for(i=0;i<m;i++)
48             if(maks<dp[i])
49                 maks=dp[i];
50         cout<<maks<<endl;
51         if(t)
52             cout<<endl;
53     }
54     return 0;
55 }

对与测试数据：
1
5
1 4 2 5 -12
4
-12 1 2 4

dp中的数据变化如下：
-12 1 2 4
1 0 1 0 0
4 0 1 0 2
2 0 1 2 2
5 0 1 2 2
-12 1 1 2 2

最后dp中的数据变成了 1 1 2 2