# 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 算法分析：

```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