PAT甲级1045 Favorite Color Stripe (30 分) 效率最高的动态规划解法-蒲公英云

PAT甲级1045 Favorite Color Stripe (30 分) 效率最高的动态规划解法

这道题另有DFS、LCS、LIS的解法。这里的解法是动态规划，优点是读一遍输入同时就能处理好，所以非常高效。

核心思想就是【当前】珠子组成手链的最大长度【等于】以这个珠子能接上【以前最长】的某条手链的长度【加一】。

#include<iostream>
using namespace std;
int n,m,x,maxs,maxp;//默认maxp指的是多个maxs中最大的位置
int pf[205],l[205];//pf存放喜爱颜色的次序，0是不喜欢；l存放以第i个次序的颜色结尾的最大的手链长度
void find(int p){
    if(p==0)return;//是不喜欢的颜色
    if(p>=maxp){//此颜色次序可排在目前最长的链子末端的颜色的后面
        maxs++;
        l[p]=maxs;
        maxp=p;
    }else{
        if(l[p]!=0){//此颜色曾经用过，直接调取之前的长度计算
            l[p]++;
            if(p>maxs){
                maxs=p;
                maxp=p;
            }
            return;
        }
        for(int j=p;j>0;j--){
            if(l[j]!=0){//此颜色次序之前的颜色出现过
                l[p]=l[j]+1;
                break;
            }
        }
        if(l[p]==0)l[p]=1;//此颜色及其前序颜色没有用过
    }
}
int main(){
    scanf("%d\n%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&x);
        pf[x]=i;
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        scanf("%d",&x);
        find(pf[x]);
    }
    printf("%d\n",maxs);
    return 0;
}