PAT.A1045 Favorite Color Stripe

​​傳回目錄​​

題意

樣例（可複制）

6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6      

//output
7      

注意點

1. 本題本題有兩種做法：最長不下降序列（LIS）和最長公共子序列（LCS）
2. 注意最長子序列中不要求所有顔色都出現，也不要求每種顔色不能重複連續出現

LIS

#include<bits/stdc++.h>
using namespace std;

int Hash[210];//映射序列成為遞增序列，不喜歡的顔色映射成1
int a[10010],dp[10010];//a存放剔除了不喜歡後的序列，dp[i]存放以i結尾的最長不下降子序列
int n,m,t,num=0;
int main(){
    memset(Hash,-1,sizeof(Hash));
    cin>>n>>m;
    for(int i=0;i<m;i++){
        scanf("%d",&t);
        Hash[t]=i;
    }
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&t);
        if(Hash[t]>=0)a[num++]=Hash[t];
    }
    int ans=-1;
    for(int i=0;i<num;i++){//最長不下降子序列模闆 
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(a[j]<=a[i]&&dp[i]<dp[j]+1){
                dp[i]=dp[j]+1;
            }
        }
        ans=max(dp[i],ans);
    }
    cout<<ans;
    return 0;
}      

1. 使用最長公共子序清單示如下圖：其中紅色為序列a，b，黃色為邊界。

LCS

#include<bits/stdc++.h>
using namespace std;

int n,m;//n用來吸收序列b出現的顔色個數，再用于存放b的長度
int a[10010],b[10010],dp[10010][10010];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)scanf("%d",&a[i]);
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=0;i<=m;i++)dp[i][0]=0;
    for(int i=0;i<=n;i++)dp[0][i]=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            int maxx=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j])dp[i][j]=maxx+1;
            else dp[i][j]=maxx;
        }
    }
    cout<<dp[m][n];
    return 0;
}