1045 Favorite Color Stripe

发表于

重点在Eva is trying to make her own color stripe out of a given one. She would like to keep only her favorite colors in her favorite order by cutting off those unwanted pieces and sewing the remaining parts together to form her favorite color stripe.
从给的例子可以看出，要求保持喜欢颜色的先后顺序，并且使最后条纹的长度尽可能长。（喜欢的颜色可以不出现）

以
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6
为列，6表示总共6种颜色，5表示喜欢5中颜色，之后是喜欢颜色的优先级顺序。
12表示原条纹的颜色排列，之后依次是12种颜色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
int book[201], a[10001], dp[10001];
int main() {
    int n, m, x, l, num = 0, maxn = 0;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d", &x);
        book[x] = i;
    }
    // book[x] = i表示x颜色的下标为i
    scanf("%d", &l);
    for(int i = 0; i < l; i++) {
        scanf("%d", &x);
        if(book[x] >= 1)
            a[num++] = book[x];
    }
    for(int i = 0; i < num; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++)
            if(a[i] >= a[j])
                dp[i] = max(dp[i], dp[j] + 1);
        maxn = max(dp[i], maxn);
    }
    printf("%d", maxn);
    return 0;
}