*PAT_甲級_1045 Favorite Color Stripe (30分) (C++)【LIS/動态規劃/晴神筆記】

目錄

1，題目描述

題目大意

輸入

輸出

說明

2，思路

核心思想

LIS問題

1，問題的定義及複雜之處 

2， 動态規劃求解問題

3，舉例

4，示例代碼

3，代碼

1，題目描述

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
           

題目大意

（一開始确實不好了解）

有一個人叫Eva，喜歡特定的顔色按照特定的順序排列，比如{2，3，1，5，6}，表示顔色2在第一位，顔色3要在2後面，顔色1要在3後面……以此類推（不必所有喜歡的顔色全部出現，剛開始一直在糾結這裡）。

這裡有一個色帶，它的顔色順序是這樣的{2 2 4 1 5 5 6 3 1 1 5 6}，現在需要計算（Eva would like to have the remaining favorite stripe with the maximum length.），按照Eva喜歡的顔色順序，最長可以拼成多長的色帶（原色帶的順序保持不變）。本例中最優解有以下幾種：{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}.

輸入

1. 第一行： 樣例中涉及到的顔色數目N；
2. 第二行：Eva喜歡的顔色數目M，M種顔色的編号及順序；
3. 第三行：彩帶長度L，依次對應的顔色種類及順序；

輸出

1. 滿足Eva喜好的顔色及順序的最大長度； 

說明

• Eva可以辨識的顔色數目不超過200；
• 顔色編号1-N； 

2，思路

這一題參考了柳神的思路，了解到這其實是一個LIS（Longest Increasing Sequence，最長不下降子序列）的一個變化（Eva喜歡的顔色中，排最前的指派最小，越往後越大。并将新設定的值替換掉原先色帶的顔色編号）。于是乎，轉戰晴神筆記，了解一下LIS問題。

核心思想

1. 重新聲明一個數組num，将Eva喜歡的顔色編号，按照先後順序重新指派，比如{2 3 1 5 6}，num[2]=1，num[3]=2，num[1]=3……
2. 在接受原色帶時，剔除Eva不喜歡的顔色，并将喜歡的顔色重新編号：

   

3. 此時問題便轉換為LIS問題，并可用動态規劃求解。時間複雜度O(n^2);

LIS問題

以下圖檔内容均來自《算法筆記》——胡凡（又稱“晴神筆記”）

1，問題的定義及複雜之處 

2， 動态規劃求解問題

3，舉例

4，示例代碼

3，代碼

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int main(){
//#ifdef ONLINE_JUDGE
//#else
//    freopen("1.txt", "r", stdin);
//#endif

    int num[201], data[10000];
    int n, m, l;                            //n涉及到的顔色數 mEva喜歡的顔色數目 l原色帶的長度
    int id, index = 0;
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        scanf("%d", &id);
        num[id] = i;                        //為顔色出現的先後順序編号
    }

    cin>>l;
    for(int i = 0; i < l; i++){
        scanf("%d", &id);
        if(num[id] > 0){                    //隻保留Eva喜歡的顔色
            data[index++] = num[id];
        }
    }

    int dp[10000], maxLen = 0;
    for(int i = 0; i < index; i++){         //原色帶處理完之後 長度為index
        dp[i] = 1;
        for(int j = i - 1; j >= 0; j--){
            if(data[i] >= data[j])
                dp[i] = max(dp[i], dp[j]+1);//動态方程
        }
        maxLen = max(maxLen, dp[i]);        //記錄最大值
    }
    cout<<maxLen;
    return 0;
}