PAT 解题报告 1045. Favorite Color Stripe (30)

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.

It is said that a normal human eye can distinguish about less than 200 different colors, so Eva’s favorite colors are limited. However the original stripe could be very long, and Eva would like to have the remaining favorite stripe with the maximum length. So she needs your help to find her the best result.

Note that the solution might not be unique, but you only have to tell her the maximum length. For example, given a stripe of colors {2 2 4 1 5 5 6 3 1 1 5 6}. If Eva’s favorite colors are given in her favorite order as {2 3 1 5 6}, then she has 4 possible best solutions {2 2 1 1 1 5 6}, {2 2 1 5 5 5 6}, {2 2 1 5 5 6 6}, and {2 2 3 1 1 5 6}.

1045. Favorite Color Stripe 算法分析:

这个题目算是有难度的了, 但是其实也就是Longest Common Subsequence的变形吧, 利用动态规划解决. 假设s[0, …, m] 和 t[0, …, n]是两个序列, 要寻找两个序列的最长公共子序列, 其中s中重叠部分可能元素会有重复出现, 设dp[m][n]表示字符序列s, t这样的最长公共子序列的长度, 我们有如下动归表达式:

dp[m][n] = max{dp[m-1][n], dp[m][n-1]}  if s[m] != t[n]
                    dp[m][n] = dp[m-1][n] + 1,              if s[m] == t[n]

实现代码如下:

#include <cstdio>

#define min(a, b) ((a) <= (b) ? (a) : (b))
#define max(a, b) ((a) >= (b) ? (a) : (b))
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;

int N, M, L;
int fav[210];
int strip[10010];

int dp[210][10010];
int gao(int m, int n) {
    if(0 == m || 0 == n) {
        return 0;
    }

    if(dp[m][n] != -1) {
        return dp[m][n];
    }

    if(fav[m-1] == strip[n-1])
    {
        dp[m][n-1] = gao(m, n-1);
        dp[m][n] = dp[m][n-1] + 1;
        return dp[m][n];
    }
    else {
        dp[m-1][n] = gao(m-1, n);
        dp[m][n-1] = gao(m, n-1);
        dp[m][n] = max( dp[m-1][n], dp[m][n-1] );
        return dp[m][n];
    }
    return -1;
}

int main(void) {
    scanf("%d", &N);
    scanf("%d", &M);
    REP(i, M) {
        scanf("%d", &fav[i]);
    }
    scanf("%d", &L);
    REP(i, L)
        scanf("%d", &strip[i]);
    REP(i, M+1) REP(j, L+1) dp[i][j] = -1;
    printf("%d\n",gao(M, L));
    return 0;
}
Written on January 19, 2014