UESTC--1300

原题链接：http://acm.uestc.edu.cn/problem.php?pid=1300

分析：dp,最长公共上升子列。对于两个序列num1[maxn],num2[maxn]:

如果num1[i]==num2[j],dp[i][j]=max(dp[i][k])+1;(k<j&&num1[i]>num2[k]).

否则dp[i][j]=dp[i-1][j].

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 1005
 6 using namespace std;
 7 int n1,n2,ans;
 8 int num1[maxn],num2[maxn];
 9 int dp[maxn][maxn];
10 void getLcis()
11 {
12     memset(dp,0,sizeof(dp));
13     for(int i=1;i<=n1;i++)
14     {
15         int k=0;
16         for(int j=1;j<=n2;j++)
17         {
18             if(num1[i]!=num2[j])dp[i][j]=dp[i-1][j];
19             if(num1[i]>num2[j]&&dp[i][j]>dp[i][k])k=j;
20             if(num1[i]==num2[j])dp[i][j]=dp[i][k]+1;
21         }
22     }
23     for(int i=1;i<=n2;i++)
24     if(dp[n1][i]>ans)ans=dp[n1][i];
25 }
26 int main()
27 {
28     int T;
29     cin>>T;
30     while(T--)
31     {
32         cin>>n1>>n2;
33         for(int i=1;i<=n1;i++)
34         scanf("%d",&num1[i]);
35         for(int i=1;i<=n2;i++)
36         scanf("%d",&num2[i]);
37         ans=-1;
38         getLcis();
39         cout<<ans<<endl;
40     }
41     return 0;
42 }
43 
44

View Code