填寫問券˙抽7-11禮券工程師靠存股年領百萬股息正妹的東京自助旅行24天後重啟院會 兩岸...
2013-02-13 20:28:00 人氣(326) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][LCIS] 12511 - Virus

0
收藏
0
推薦


  Virus 

We have a log file, which is a sequence of recorded events. Naturally, the timestamps are strictly increasing.

However, it is infected by a virus, so random records are inserted (but the order of original events is preserved). The backup log file is also infected, but since the virus is making changes randomly, the two logs are now different.

Given the two infected logs, your task is to find the longest possible original log file. Note that there might be duplicated timestamps in an infected log, but the original log file will not have duplicated timestamps.

Input 

The first line contains T (T$ le$100), the number of test cases. Each of the following lines contains two lines, describing the two logs in the same format. Each log starts with an integer n ( 1$ le$n$ le$1000), the number of events in the log, which is followed by n positive integers not greater than 100,000, the timestamps of the events, in the same order as they appear in the log.

Output 

For each test case, print the number of events in the longest possible original log file.

Sample Input 

1
9 1 4 2 6 3 8 5 9 1
6 2 7 6 3 5 1

Sample Output 

3



Problemsetter: Rujia Liu, Special Thanks: Yiming Li, Jane Alam Jan


求最長共同遞增子序列
有一點掃描線的結構,效率 O(nm)。


#include <stdio.h>

int main() {
    int t, n, m, a[1505], b[1505];
    int i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d", &a[i]);
        scanf("%d", &m);
        for(i = 0; i < m; i++)
            scanf("%d", &b[i]);
        int LCIS[1505] = {};
        for(i = 0; i < n; i++) {
            int tmp = 0;
            for(j = 0; j < m; j++) {
                if(a[i] == b[j] && LCIS[j] < tmp+1)
                    LCIS[j] = tmp+1;
                if(a[i] > b[j] && LCIS[j] > tmp)
                    tmp = LCIS[j];
            }
        }
        int res = 0;
        for(i = 0; i < m; i++)
            if(LCIS[i] > res)
                res = LCIS[i];
        printf("%d\n", res);
    }
    return 0;
}

12511VirusLCISDP
台長:Morris
人氣(326) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][BWT逆轉換] 741 - Burrows Wheeler Decoder
此分類上一篇:[UVA] 12571 - Brother & Sisters!

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文