[PAT解题报告] Favorite Color Stripe
给定一些喜欢的颜色（整数）还有一些颜色的布条，布条是有顺序的。选择布条必须按照布条自己的顺序，排列布条需要按照喜欢颜色的顺序来排列，也就是说对每个布条选择要还是不要，最后按照原来布条的把要的布条连接起来形成每种要的布条的先后顺序必须符合原来喜欢布条的顺序，求最后最长能拥有多少个布条。
一个显然的动态规划。喜欢的颜色可以自己重新编号，表示喜欢的第i种颜色。dp[x]表示目前以喜欢的第x种颜色结尾的最长选择的布条数。
当然第i块布条恰好是第x种颜色时，我们可以倒推之前选出的是哪种颜色布条结尾。注意之前结尾的必须是y <= x, 所以dp[x] =
max(max(dp[y] + 1) , dp[x])。注意y == x时更新的顺序。
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int state[202],dp[202];
int main() {
int n,m;
scanf("%d%d",&n,&m);
memset(state,0xff,sizeof(state));
for (int i = 1; i <= m; ++i) {
int x;
scanf("%d",&x);
state[x] = i;
}
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
int x;
scanf("%d",&x);
if ((x = state[x]) >= 0) {
for (int y = x; y >= 0; --y) {
dp[x] = max(dp[x], dp[y] + 1);
}
}
}
n = 0;
for (int i = 0; i <= m; ++i) {
n = max(n, dp[i]);
}
printf("%d\n",n);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1045
谷歌公司福利 178人发布
查看6道真题和解析