PAT甲级A1045---动态规划最长不下降子序列

1045 Favorite Color Stripe (30分)

1045

分析：

第一行给出Eva喜欢的颜色数，第二行给出Eva喜欢颜色的顺序。第三行给出颜色序列，要求去除掉Eva不喜欢的颜色，然后再找出Eva喜欢颜色顺序的最长子序列（不一定要出现所有喜欢的颜色）。

1.最长不下降子序列

把eva喜欢的顺序映射为0,1,2...，再读入颜色序列时，剔除不喜欢的颜色，把喜欢的颜色映射之后存入数组中。

C++:

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxl = 10010;
const int maxm = 210;

int hashTable[maxm], arr[maxl], dp[maxl];

int n, m, l;

int main() {
    scanf("%d", &n);
    scanf("%d", &m);
    fill(hashTable, hashTable + maxm, -1);
    int x;
    for (int i = 0; i < m; i++) {
        scanf("%d", &x);
        hashTable[x] = i;
    }
    scanf("%d", &l);
    int num = 0;
    for (int i = 0; i < l; i++) {
        scanf("%d", &x);
        if (hashTable[x] != -1) {
            arr[num++] = hashTable[x];//注意此处arr数组中存储的是hashTable[x]
        }
    }
    dp[0] = 1;
    for (int i = 1; i < num; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] <= arr[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }
    int max = -1;
    for (int i = 0; i < num; i++) {
        if (dp[i] > max) {
            max = dp[i];
        }
    }
    printf("%d\n", max);
    return 0;
}

2.最长公共子序列

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxm = 210;
const int maxl = 10010;
int A[maxm], B[maxl], dp[maxm][maxl];

int main() {
    int n, m, l;
    scanf("%d", &n);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &l);
    for (int i = 1; i <= l; i++) {
        scanf("%d", &B[i]);
    }
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (int i = 0; i <= l; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= l; j++) {
            int MAX = max(dp[i - 1][j], dp[i][j - 1]);
            if (A[i] == B[j]) {
                dp[i][j] = MAX + 1;
            } else {
                dp[i][j] = MAX;
            }
        }
    }
    printf("%d\n", dp[m][l]);
    return 0;
}