PAT 甲级 1045 1045 Favorite Color Stripe（30 分） 低耗时AC
原题地址：PAT Adv 1045
题目原文：
1045 Favorite Color Stripe（30 分）
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}.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤200) which is the total number of colors involved (and hence the colors are numbered from 1 to N). Then the next line starts with a positive integer M (≤200) followed by M Eva's favorite color numbers given in her favorite order. Finally the third line starts with a positive integer L (≤104) which is the length of the given stripe, followed by L colors on the stripe. All the numbers in a line a separated by a space.
Output Specification:
For each test case, simply print in a line the maximum length of Eva's favorite stripe.
Sample Input:
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6
Sample Output:
7题目要求：
作者: CHEN, Yue
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB
题目说明：
这道题只是求解最长不下降子串的长度。这道题给出的排序序列长度比较小（[1,N]，N<=200），我们可以在读入待评估的长串时将颜色序列的排序排名写入长串数组，而不是初始的颜色值。例如输入样例的颜色2位于最喜欢颜色的第一位，那么该颜色排序排名就是1（rank[2]=1），那么在读入长串的第一位2时，我们将长串的第一位认为是rank[2]=1就好。对于索引使得rank[]数组为0的数字，我们认为它不是喜欢的颜色，不考虑。这样，颜色长串就可以转化为颜色排序排名的长串（Seq [] 数组），那么此时求得的最终结果在颜色排序排名长串中是排名（值）不下降的。
另外，我们引入辅助数组Len[]。在评估长串（Seq[]数组）中某一个元素时Seq[ i ]，Len[ j ]代表考虑了之前的所有元素后子串结尾排名为 j 时所能达到的最大长度。那么对于当前需要新考虑的元素Seq[ i ]来说，以结尾排名为Seq[ i ]的子串所能达到的最大长度应该是之前考虑的子串结尾排名小于等于（即不下降）Seq[ i ]的最大长度的最大值。换句话说 新的Len[ Seq[i] ]应该等于max(Len[ j ])+1,其中j的取值范围为[1, Seq[ i ] ], 这样才能满足最长不下降的特点，同时更新了以当前正在考虑的Seq[i]做为子串结尾排名的最长长度。所有的Seq[]数组元素考虑完后，就可以遍历 Len[]数组求的最长子串的长度，例如Len[]数组的最大值在Len[ j ]处取得，那么最长不下降子串的结尾颜色排名应为 j 。
进一步想，在访问Seq[]数组的某一个元素时，不会对该数组的其它元素产生影响，也无需在访问该元素时访问之前的元素，故该数组可以简化为一个整数变量。从而降低了空间复杂度。该方法的空间复杂度为O(N)，使用两个长度为颜色集合的数量的数组，一个为rank[]数组，一个为Len[]数组。该方法的时间复杂度为O(N*L)，其中N代表颜色集合的数量（<=200），而L则代表长串长度（<=10000），也很容易理解，因为对于每个长串元素来说，我们需要遍历小于等于该元素颜色排名的排名作为子串结尾的最大长度数组，即Len[]数组的索引从1至该元素颜色排名。
完整AC代码：
#include<cstdio>
#define max(a,b) (a)>(b)?(a):(b)
int N, M, L, tmp_color, tmp_rank, ans=0, rank[205] = {0}, Len[205]={0};
/*
N : element number of color set
M : element number of pre-ordered color set
L : element number of colors to be assessed
tmp_color : temporary color id
tmp_rank : temporary color rank, according to pre-ordered color order
ans : answer we desire
rank[] : rank[color-id] = color-rank-order
Len[] : Len[rank-of-seq-end-element] = max-seq-length
*/
int main(){
scanf("%d %d",&N,&M);
for(int i=1;i<=M;i++){
scanf("%d",&tmp_color);
rank[tmp_color]=i; //construct rank matrix
}
scanf("%d",&L);
while(L--){
scanf("%d",&tmp_color);
if( (tmp_rank=rank[tmp_color]) ){ //if current color is a favorite color
int max_len=0;
for(int i=1;i<=tmp_rank;++i)
max_len=max(max_len,Len[i]); //acquire the the max-sequence-length that ends with current assessing color rank
Len[tmp_rank]=max_len+1; //update the max-sequence-length that ends with current assessing color rank
ans=max(ans,Len[tmp_rank]); //update answer
}
}
printf("%d",ans);
return 0;
}
运行时间截图：
进一步想，对于数组快速求最值问题，我们还可以使用线段树进行优化。
线段树+快速输入+动规 代码：
#include<bits/stdc++.h>
using namespace std;
/**
segment tree
*/
int const maxn=2e2+5;
int sum[maxn<<2] = {0};
void update(int L,int C,int l,int r,int rt){
if(l==r)
sum[rt]=C;
else{
int m=(l+r)>>1;
if(L<=m)
update(L,C,l,m,rt<<1);
else
update(L,C,m+1,r,rt<<1|1);
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
}
int query(int L,int R,int l,int r,int rt){
if(L<=r && r<=R)
return sum[rt];
else{
int ans=0, m=(l+r)>>1;
if(L<=m)
ans=max(ans,query(L,R,l,m,rt<<1));
if(R>m)
ans=max(ans,query(L,R,m+1,r,rt<<1|1));
return ans;
}
}
/**
accelerated read in
*/
int read(){
int input=0;
char a=getchar();
while(a<'0' || a>'9')
a=getchar();
while(a>='0' && a<='9'){
input=input*10+a-'0';
a=getchar();
}
return input;
}
/**
LCS
*/
int n, m, l, max_len, tmp_color, tmp_rank, order[205]={0};
int main(){
n=read(), m=read();
for(int i=1;i<=m;++i)
order[read()]=i;
l=read();
while(l--){
tmp_color=read();
if( (tmp_rank=order[tmp_color]) ){
max_len=query(1,tmp_rank,1,m,1); //查询[1,tmp-rank]范围内的最大长度max_len
update(tmp_rank,max_len+1,1,m,1); //更新tmp_rank位置的的值为max_len+1
}
}
printf("%d",sum[1]);
return 0;
}
此时程序运行时间：
虽然相较于第一段代码没有运行时间的显著降低，但是此时代码的时间复杂度对于颜色排序集合的数量M更加的不敏感，从第一段的O(M*N)降低为第二段代码的O(log2(M)*N)。我们姑且认为，这里效率体现的不明显是因为颜色排序集合的数量M不够大导致的。
或者使用树状数组。
树状数组代码：
#include<cstdio>
using namespace std;
#define INT_MIN 0x80000000
#define max(a,b) (a)>(b)?(a):(b)
#define lowbit(x) ( (x)&(-x) )
/*
c[] matrix is the tree array of Len[] matrix,
which is no need to be restored in this case
*/
int n, m, l, tmp_color, tmp_order, max_len, c[205] = {0}, order[205] = {0};
// return the maximum value of Len[] matrix from index 1 to R, inclusive.
int max_R(int R){
int ans=INT_MIN;
while(R>0){
ans=max(ans,c[R]);
R-=lowbit(R);
}
return ans;
}
/*
update the tmp value to Len[index] & update the c[] matrix,
where tmp is greater than the original Len[index]
*/
int update(int index,int tmp){
while(index<=m){
c[index]=max(c[index],tmp);
index+=lowbit(index);
}
}
/*
accelerated read in
*/
int read(){
int input=0;
char a=getchar();
while(a<'0' || a>'9')
a=getchar();
while(a>='0' && a<='9'){
input=input*10+a-'0';
a=getchar();
}
return input;
}
int main(){
n=read(), m=read();
for(int i=1;i<=m;++i){
tmp_color=read();
order[tmp_color]=i;
}
l=read();
while(l--){
tmp_color=read();
if(tmp_order=order[tmp_color]){
max_len=max_R(tmp_order);
update(tmp_order,max_len+1);
}
}
printf("%d",max_R(m));
return 0;
}
此时的运行时间达到了最高3 ms：
参考：
上一篇： QT解决中文乱码