PAT甲级1045.

目录

A1045

题目

样例

输入:

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

输出:

7

思路和坑点

　　将喜欢的序列映射成一个递增的序列，然后将给出的序列中使用动态规划的方式找到最长不下降子序列即可（动态规划的求解思路参见动态规划的总结）

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n;
    scanf("%d",&n);                        //过滤第一个数字，其实第一个数字没有用处 
    scanf("%d",&n);                        //读入喜欢的序列 
    unordered_map<int,int> mp;            //按照升序映射 
    for(int i=1;i<=n;i++){
        int temp;
        scanf("%d",&temp);
        mp[temp]=i;
    }
    scanf("%d",&n);                        //读取提供的序列 
    vector<int> v;
    for(int i=0;i<n;i++){                //如果没有喜欢的直接略过，不保存 
        int temp;
        scanf("%d",&temp);
        if(mp.find(temp)!=mp.end())        //按照映射的方式加入序列 
            v.push_back(mp[temp]);
    }
    if(v.size()==0){                    //如果没有喜欢的颜色，特判输出0 
        cout<<0;
        return 0;
    }
    int ans=1;                            //如果有喜欢的颜色，则至少为1 
    vector<int> dp(v.size(),1);            //动态规划计算最长不下降子序列（可连续，也可以不连续） 
    for(int i=1;i<v.size();i++){
        for(int j=0;j<i;j++){
            if(v[j]<=v[i]&&dp[j]+1>dp[i]){
                dp[i]=dp[j]+1;
            }
        }
        ans=max(ans,dp[i]);                //保存最长的序列 
    }
    cout<<ans;
    return 0;
}