【PAT甲級】1045. Favorite Color Stripe (30)

動态規劃：最長非連續子序列類似題目

注：最後兩個測試用例容易逾時，需要進行優化

#include <stdio.h>

int n, m, l;
int in[];
int order[];
int getLongest(int *a, int *b, int m, int l);

int main(int argc, char *argv[]) {
    int n, m, l;
    int i, j;
    scanf("%d", &n);
    for (i = ; i < ; i++) {
        in[i] = ;
        order[i] = ;
    }
    scanf("%d", &m);
    int *a = new int[m];
    for (i = ; i < m; i++) {
        scanf("%d", &a[i]);
        in[a[i]] = ;
        order[a[i]] = i;
    }
    scanf("%d", &l);
    int *b = new int[l];
    int cnt = ;
    for (i = ; i < l; i++) {
        int tmp;
        scanf("%d", &tmp);
        if (in[tmp] == ) {
            b[cnt++] = tmp;
        }
    }
    l = cnt;
    int out = getLongest(a, b, m, l);
    printf("%d\n", out);
    return ;
}
int getLongest(int *a, int *b, int m, int l) {
    int *d = new int[l];
    int len = ;
    for (int i = ; i < l; i++) {
        d[i] = ; 
        for (int j = ; j < i; j++) {
            if (order[b[j]] <= order[b[i]] && d[i] < d[j] + ) {
                d[i] = d[j] + ;
            }
        }
        if (len < d[i]) len = d[i];
    }
    return len;
}