csuoj 1120:ウイルス

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1120
1120:ウイルス
Time Limit: 3 Sec  Memory Limit: 128 MBSubmit: 513  Solved: 209[ Submit ][ Status ][ Web Board ]
Description
さまざまなシステムイベントの詳細が記録されたログファイルがあります.自然に、イベントのタイムスタンプは厳格なインクリメント順に並べられます(2つのイベントが完全に同じ時刻に発生することはありません).
残念なことに、あなたのシステムはウイルスに感染し、ログファイルにウイルスが生成したランダムな擬似イベントが混入しています(実際のイベントの相対的な順序は変わりません).バックアップされたログファイルも感染していますが、ウイルスが採用しているランダム感染方法のため、プライマリ・ログ・ファイルとバックアップ・ログ・ファイルは感染後に異なる可能性があります.
感染したプライマリ・ログとバックアップ・ログを与え、実際のイベント・シーケンスの最長可能な長さを求めます.
 
Input
第1動作データ群数T(T<=100)を入力する.各グループのデータには、感染後のプライマリ・ログとバックアップ・ログの2行が含まれます.
各ログファイルのフォーマットは同じで、1つの整数n(1<=n<=1000)(感染後のイベントの総数を表す)と、n個の100000を超えない正の整数(感染後の各イベントを表すタイムスタンプ)である.
感染後、タイムスタンプが全く同じイベントが発生する可能性があります.
Output
各データのセットについて、実際のイベントシーケンスの最大可能な長さを出力します.
Sample Input

1

9 1 4 2 6 3 8 5 9 1

6 2 7 6 3 5 1

Sample Output

3

HINT
 
Source
湖南省第8回大学生コンピュータプログラム設計コンテスト
 
 
分析;
 
最長の共通増分サブシーケンスを求めます.
 
ACコード:

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 using namespace std;

 5 

 6 int a[1010], b[1010], dp[1010][1010];

 7 

 8 int main()

 9 {

10     int t, n, m, i, j, k;

11     scanf("%d",&t);

12     while(t--){

13         scanf("%d",&n);

14         for(i=1; i<=n; i++) scanf("%d",&a[i]);

15         scanf("%d",&m);

16         for(i=1; i<=m; i++) scanf("%d",&b[i]);

17         memset(dp, 0, sizeof(dp));

18         for(i=1; i<=n; i++){

19             int maxx=0;

20             for(j=1; j<=m; j++){

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

22                 if(a[i]>b[j]) maxx=max(maxx, dp[i-1][j]);

23                 else if(a[i]==b[j]) dp[i][j]=maxx+1;

24             }

25         }

26         int M=0;

27         for(i=1; i<=m; i++)

28             M=max(M, dp[n][i]);

29         printf("%d
", M);

30     }

31     return 0;

32 }

View Code