UVa10534 - Wavio Sequence(LIS, 動態規劃)

題目大意

我們定義 Wavio Sequence

• 長度必須是 \(2 * n + 1\)
• 前 \(n+1\) 個數字必須遞增
• 後 \(n+1\) 個數字必須遞減
  接下來會給你一個數列，請你在這些數字中找出 最長 Wavio Sequence

題目連結

重點觀念

• LIS 的應用
• 將每一個 index 的 LIS 長度都記錄下來

分析

• Wavio Sequence 可以看成前半段是 LIS、後半段是 LDS(最長遞減子序列)
• 那我們可以從左至右、從右至左各做一次 LIS，並且用兩個陣列紀錄每個數列位置的最長 LIS、LDS 長度
  注意：從右至左做一次 LIS，就是從左至右做一次 LDS
• 找出在同個數列 index 下中 \(min(LIS,LDS) * 2 + 1\)，即可。
• 有些小細節，我在程式裡說明

參考連結

Uva10534 - Wavio Sequence by txya900619

心得

LIS 很多小細節處理其實我也沒有學得很精，希望自己可以好好學習好。注意這些問題，加強自己的思考能力。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 10020
using namespace std;
int n, temp;
//num 題目數列, lis_index 最長的 LIS 長度，lds 也是
int num[MAXN], lis_index[MAXN], lds_index[MAXN]; 
deque<int> lis, lds;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> n){
        lis.clear(); lds.clear();
        for(int i = 0; i < n; i++) cin >> num[i];

        //LIS
        lis.push_back(num[0]);
        lis_index[0] = 0;
        for(int i = 1; i < n; i++){
            if(num[i] > lis.back()){
                //要稍微注意，因為我們 LIS 下方的 else 在輸入 lis_index[i] 是會根據 deque.size()，
                //但 deque.size() 從 0 開始計數，所以我們這邊的 lis_index[i] 也從 0 開始計數，
                //因此當 lis_index[i] = 0，都內含自己。
                lis_index[i] = lis.size(); //be careful, lower_bound => deque.size(). NOT LIS length
                lis.push_back(num[i]);
            }
            else{
                //大衛的筆記是用 upper_bound，是因為那篇實作 LIS 是大於等於都可以，但這裡僅限大於
                temp = lower_bound(lis.begin(), lis.end(), num[i]) - lis.begin();
                lis [temp] = num[i];
                lis_index[i] = temp;
            }
        }

        //LDS，解釋與上方相同
        lds.push_back(num[n-1]);
        lds_index[n-1] = 0; //要先歸為零，不然會跟其他測資混亂。
        for(int i = n-2; i >= 0; i--){
            if(num[i] > lds.back()){
                lds_index[i] = lds.size();
                lds.push_back(num[i]);
            }
            else{
                temp = lower_bound(lds.begin(), lds.end(), num[i]) - lds.begin();
                lds[temp] = num[i];
                lds_index[i] = temp;
            }
        }

        int ans = 0;
        for(int i = 0; i < n; i++){
            //cout << "i lis lds " << i << " " << lis_index[i] << " " << lds_index[i] << "\n";
            
            //由於 Wavio Sequence 必須左右長度都是 n+1, 因此我們就以 i 為單位，
            //使用最小的 LIS or LSD 長度，
            //但由於我們計數都是從 0 開始，別忘了 + 1(自己)
            //+1 原因，我們是以 num[i] 為中心算最長長度，因此重複用到一次。
            //但因為我們計數都是從 0 開始，所以從 (2*n)-1 改為 (2*n)+1
            ans = max(ans, min(lis_index[i], lds_index[i]) * 2 + 1);
        }
        cout << ans << '\n';
    }

    return 0;
}