UVa10192 - Vacation (LCS)

題目大意：

爸媽想要出國出去玩，可是今年有疫情欸，拔麻，反正爸媽不管且還要求出國的遊玩順序一定要按照他們想法，這讓我非常煩惱，但他們願意略過一些他們想去的地方，但順序必須一樣，試問如果爸媽都有自己的出國遊玩順序再不影響他們順序時他們可以去的最大長度？

注意：這題輸入字串會有 space , uppercase letters , lowercase letters
所以要使用 getline(string,cin) 會是最好的方法

分析：

這題是標準的 LCS 問題，可以用 \(O(n^2\) and \(O(n \log n) \) 解開，這裡使用 \(O(n \log n)\) 來解決此問題。

如果還不太懂 LCS 是甚麼問題，建議看看 演算法知識 - Longest Common Subsequence 最長共同子序列(時間複雜度 O(nlogn))，這裡有對於此演算法有完整的介紹

焦點回到題目上，解開題目的小設計

記住他的輸出還要輸出一些文字，不是只直接輸出 LCS 的長度即可。

P.S. 下方題目程式碼的 string index 由 1 開始方便編寫程式碼，主要方便用來 LIS 如果要更改 cur 成 0 時會造成 t[-1] ，只需要在 string = "$" + string，即可達到此功效

心得

這題其實沒有很難，但是我搞了很久因為 udebug 壞掉了，嗚嗚嗚，沒有 Udebug 我就超像一個白癡一樣甚麼都不會，不可以阿大衛，這樣你打 ICPC 怎麼會進步呢QQ，讓我發現我對 Udebug 就像是小孩子依賴麻麻一般，要是沒有了她我則甚麼都不會。

盡量不要這樣，可能需要增進自己去 hack 測試資料的能力並想出自己程式碼的漏洞，不過明明寫出自己覺得沒有錯的程式碼然後想錯誤，其實也是一件蠻痛苦的事情呢XD。

題目程式碼

其實就是沒有附上說明的程式碼，看得懂跟說得出來真的是兩回事，也許還有人覺得我說的很差，不過我已經盡力解釋。希望可以幫助到各位。

也希望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

於是這裡就補述一些題目給的資料範圍限制與標頭檔了。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define N 120
using namespace std;
int n ;
string strA , strB ;
int t[N*N] , d[N*N] , num[N*N] ; //determine
map<char,vector<int>> dict ;

int bs(int l , int r , int v ){
    int m ;
    while(r>l){
        m = (l+r) /2 ;
        if(num[v] > num[t[m]]) l = m+1 ;
        else if (num[v] < num[t[m]]) r = m ;
        else return m ;
    }
    return r ;
}

int lcs(){
    dict.clear() ;
    for(int i = strA.length()-1 ; i > 0 ; i--) dict[strA[i]].push_back(i) ;

    int k = 0 ;
    for(int i = 1 ; i < strB.length() ; i++){
        for(int j = 0 ; j < dict[strB[i]].size() ; j++)
            num[++k] = dict[strB[i]][j] ;
    }
    if(k==0) return 0 ;
    //memset(t ,-1 , sizeof(t));
    d[1] = 0 , t[1] = 1 ;
    int len = 1, cur ;

    for(int i = 1 ; i <= k ; i++ ){
        if(num[i] > num[t[len]]) t[++len] = i , d[i] = t[len-1] ;
        else{
            cur = bs(1,len,i);
            t[cur] = i ;
            d[i] = t[cur-1];
        }

        //debug
//        for(int i = 1 ; i <= k ; i++)
//            cout << num[t[i]] << ' ' ;
//        cout << '\n' ;
    }
    return len ;

}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin ) ;
    freopen("out.txt" , "w" , stdout) ;
#endif // LOCAL
    n = 1 ;
    while(getline(cin,strA) && strA != "#"){
        getline(cin,strB);
        strA = "$" + strA;
        strB = "$" + strB;
        //cout << lcs() << '\n' ;
        cout << "Case #" << n++ << ": you can visit at most " << lcs() << " cities.\n";
    }
    return 0;
}