[最長公共子序列]杭電 HDU 1423 Greatest Common Increasing Subsequence

[cpp] 
/* THE PROGRAM IS MADE BY PYY */ 
/*----------------------------------------------------------------------------//
    Copyright (c) 2012 panyanyany All rights reserved.
 
    URL   :
    Name  : 1423 Greatest Common Increasing Subsequence
    Classification : 最長公共子序列
 
    Date  : Wednesday, July 11, 2012
    Time Stage : two hour
 
    Result:
6178365 2012-07-11 11:46:23 Accepted    1423
15MS    236K    1670 B
C++ pyy
 
 
Test Data :
 
Review :
//----------------------------------------------------------------------------*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
#include <vector> 
 
#include <algorithm> 
#include <iostream> 
#include <queue> 
#include <set> 
#include <string> 
 
using namespace std ; 
 
#define MEM(a, v)        memset (a, v, sizeof (a))    // a for address, v for value 
#define max(x, y)        ((x) > (y) ? (x) : (y)) 
#define min(x, y)        ((x) < (y) ? (x) : (y)) 
 
#define INF     (0x3f3f3f3f) 
#define MAXN    (1005) 
 
#define L(x)    ((x)<<1) 
#define R(x)    (((x)<<1)|1) 
#define M(x, y) (((x)+(y)) >> 1) 
 
#define DB    // 
 
int a[MAXN], b[MAXN], dp[MAXN]; 
 
int GCIS(int n1, int n2) 
{ 
    int i, j, pos; 
    MEM(dp, 0); 
    for (i = 1; i <= n1; ++i) 
    { 
        pos = 0; 
        for (j = 1; j <= n2; ++j) 
        { 
            // 遍歷b的同時，找出 j 之前最大的公共子序列所在點 pos，並且要使 b[pos] < a[i] 
            // 這樣，當下一句 b[j]==a[i] 時，就可以直接得到 j 點的最大公共子序列了：dp[pos]+1 
            // 像 dp[j-1]+1，或者 dp[j]+1 之類的，都不能保證結果最優。 
            if (b[j] < a[i] && dp[pos] < dp[j]) 
            { 
                pos = j; 
            } 
 
            if (b[j] == a[i]) 
                dp[j] = dp[pos] + 1; 
        } 
    } 
    j = 0; 
    for (i = 1; i <= n2; ++i) 
        j = max(j, dp[i]); 
 
    return j; 
} 
 
int main() 
{ 
    int i, n1, n2, tc; 
    while (scanf("%d", &tc) != EOF) 
    {   www.2cto.com
        while (tc--) 
        { 
            scanf("%d", &n1); 
            for (i = 1; i <= n1; ++i) 
                scanf("%d", a+i); 
            scanf("%d", &n2); 
            for (i = 1; i <= n2; ++i) 
                scanf("%d", b+i); 
 
            printf("%d\n", GCIS(n1, n2)); 
            if (tc) 
                putchar('\n'); 
        } 
    } 
    return 0; 
} 

 作者：panyanyany