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

客官°小女子只卖身不卖艺 2023-06-11 09:22 45阅读 0赞

这道题另有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;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70][]

[https://www.liuchuo.net/archives/2283][https_www.liuchuo.net_archives_2283]

上面给的解法属于更常规的解法，最后两个测试点的时间长一些，也是非常好的，对考试完全够用了：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70 1][]

给出一个我自用的测试点，用来过测试点2（模拟全是不喜欢的颜色，6分）：

6
    5 1 2 3 4 5
    3 6 6 6

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70]: /images/20230531/acb4f8cc0d2c4e60912b538b7cd218ad.png
[https_www.liuchuo.net_archives_2283]: https://www.liuchuo.net/archives/2283
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsbGlzb25zaGluZw_size_16_color_FFFFFF_t_70 1]: /images/20230531/c036493c642f4fd5b0b53720ec0b780a.png