hdu 1423 最长公共递增子序列

 1 #include<iostream>
 2  #include<stdio.h>
 3  #include<string.h>
 4  #include<algorithm>
 5  using namespace std;
 6 
 7  int a[1005],b[1005];
 8  int ss[1005];
 9  int dp[1005][1005];
10  int LCIS(int n,int m)
11  {
12      int k;
13      int sum=0;
14      for(int i=1;i<=n;i++)
15      {
16          k=0;
17          for(int j=1;j<=m;j++)
18          {
19              dp[i][j]=dp[i-1][j];
20              if(a[i]==b[j])
21                 //ss[j]=k+1;
22                dp[i][j]=k+1;
23              else if(a[i]>b[j])
24              {
25                  //if(k<ss[j])
26                    // k=ss[j];
27                     if(k<dp[i-1][j])
28                     k=dp[i-1][j];
29              }
30          }
31      }
32      for(int i=1;i<=m;i++)
33        //sum=max(sum,ss[i]);
34        if(sum<dp[n][i])
35          sum=dp[n][i];
36 
37        return sum;
38  }
39  int main()
40  {
41      int t,n,m,ans;
42      scanf("%d",&t);
43      while(t--)
44      {
45          memset(ss,0,sizeof(ss));
46          scanf("%d",&n);
47         for(int i=1;i<=n;i++)
48             scanf("%d",&a[i]);
49         scanf("%d",&m);
50         for(int i=1;i<=m;i++)
51             scanf("%d",&b[i]);
52        ans=LCIS(n,m);
53        printf("%d\n",ans);
54        if(t)
55         printf("\n");
56      }
57 
58  }