UVa 111 - History Grading (LIS)

題目大意：

老師要改考卷關於歷史的事件排序，我們要寫程式幫老師解決其中一道題目，簡單來說，歷史有很多事件，只要學生們排序歷史事件順序有對，就給予相對應的分數，我們將歷史事件定義成數字，順序則就是數學的遞增。

1,2,3,4 得四分 因為遞增的數列最長可以來到 4
2,1,3,4 得三分，因為 1,3,4 or 2,3,4 這樣的順序都有正確，但順序長度只有 3，所以就輸出 3 分
4,3,2,1 得一分，有這四種 1 or 2 or 3 or 4，而他們遞增長度最高都只能來到 1，因此只有一分。

我們就是要找出，最長的數值遞增長度。

這題的格式： 1 3 2 4 ，其中 1 是表示歷史事件 1 是在第 1 個位置、 3 則是表示歷史事件 2 是在第三個位置，全部的數值都是用此表達方式表達。

分析：

看得出來嗎XD，這題其實就是詢問你最長的 LIS 長度。

這題就是標準的最長遞增子序列 Longest Increasing Subsequence (以下簡稱 LIS) 問題，這裡使用 \(O(n \log n)\) 來解決此問題。

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

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

這題有個巨大的坑，他並不是一開始就排好順序的，他有一個特殊格式，還有在題目卷下寫一個 warning，要你好好看懂。那時候我還以為我自己有看懂了，英文差的人就是這麼爛嘛 ಥ⌣ಥ

重點是我還花了兩小時！完全沒有找出錯誤…，看別人的解答才知道…，我好爛QQ。

於是我們要怎麼解決這個問題呢，index 上的值是 rank(他們的順序)，其實這裡有點腦筋急轉彎，我還以為出題者可能就是要考這個呢XD。

先直接將老師的答案直接存到陣列中，我們舉例一下：

正確解答： 3 2 1 4 ，我們定義正確解答為 a[]
你的答案： 2 1 3 4 ，我們定義你的答案為 b[]

於是我們先這樣做

a[1] = 3 //因為 1 應該要排在第 3 個位置，我們先透過 a 進行記錄
a[2] = 2
a[3] = 1
a[4] = 4 

// 透過此方式可以直接產生符合題目要求且方便 LIS 撰寫的陣列
b[2] = a[1] = 3  // 由於你的答案歷史事件 1 的 rank 是 2，表示他應該是要在生成數列中的第二個位置，因此設定成 b[2]
// a[1] 則是 1 事件的 rank 位置，也就是他其實是第 3 個發生的事情，所以 b[2] = 3
b[1] = a[2] = 2 
b[3] = a[3] = 1
b[4] = a[4] = 4

透過此方式可以得知，b[] 按照 index 順序並從 1 開始應該是這樣的 2 3 1 4，肉眼不難找出最長的 LIS 有 3，且為 2 1 4，我們再來驗證看是否正確，對的，沒錯正確解答與你的解答確實 2 1 4 有符合順序，因此得證。

OK，解開題目得小設計後，其他就與 LIS 沒有不同拉XD，記住要用迴圈寫就好，不可以手寫喔，會累死你的。

參考連結：

UVa 111 History Grading （簡單DP，LIS或LCS）

心得：

老話一句，英文很重要QQ，我到底因為英文不好吃了幾次虧啦…，好討厭。這麼簡單的一個題目我也可以拖 3 個小時都沒辦法解開而且還是錯在這種腦筋急轉彎的部分，是欺負我英文不好跟嫌我腦袋太笨嘛ಥ⌣ಥ，不行，我要讀好英文、增加自己的思維，成為一個優秀的人不會被再被這種問題給打倒，如果我沒辦法當一位聰明的人，至少我要當一個很有經驗的人！

題目程式碼

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

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define N 25
using namespace std;
int a[N] , b[N] , t[N] , d[N] , n ;
map<int,int> dict ;

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

int lis(){
    int len = 1 , cur ;
    d[1] = 0 , t[1] = 1 ;
    for(int i = 2 ; i <= n ; i++){
        if(b[i] > b[t[len]] ){
            d[i] = t[len] ;
            t[++len] = i ;
        }
        else{
            cur = bs(1,len,i);
            t[cur] = i ;
            d[i] = t[cur-1] ;
        }
    }
    return len ;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin);
    //freopen("out.txt" , "w" , stdout);
#endif // LOCAL
    cin >> n ;
    int j , temp ;
    for(int i = 1 ; i <= n ; i++){
        cin >> temp ;
        a[i] = temp ;
    }

    while(cin >> j ){
        b[j] = a[1]  ;
        for(int i = 2 ; i <= n ; i++){
            cin >> temp ;
            b[temp] = a[i] ;
        }
        //debug
        //for(int i = 1 ; i <= n ; i++) cout << b[i] << ' ' ;
        cout << lis() << '\n' ;
    }

    return 0;
}