ACM 481 What Goes Up

Longest Increasing Subsequence問題。
用正常的O(n ^ 2)的演算法去解竟然會TL，傻眼……
結果只好開始看別人是怎麼AC的。
結果AC一定要用O(nlogn)的演算法……
就開始看……我發現我看不懂 ToT。

反正就是找了一堆資料，然後寫法都很數學式，又是英文，
而且又沒範例 = =，只能說GG啊。

最後還是在這裡，
找到範例碼，真是揪甘心～

重點就是要了解Patience sorting的運作原理即可。
Patience sorting大概是這樣：
1.如果沒有pile，就做一個pile。
2.每次把x值與pile最上的值相比，若x值 < pile的top值，
就把x放到該pile上。
若無，就再做一個pile。
3.反覆，到沒有x值為此。

這樣講可能很複雜，直接舉實例說明：
-7 10 9 2 3 8 8 1。
一開始是-7，沒pile，所以給-7一個pile：
-7，
接著是10，10 > -7，所以make a new pile：
-7
10，
再來是9， 9 > -7，所以不能放在pile1，
但9 < 10，所以放在pile2上，
-7
10 9，
反覆此動作我們最後可以得到：
-7
10 9 2 1
3
8
（因為Patience sorting是針對撲克牌做sort，
所以有重複的數字，我們就不再處理第二次）
如此，我們得到4個pile。
也就是lis為4。
第1到第4個位置分別可以放-7、10 9 2 1、3、8。
注意，上面這個例子並不表示，所有lis為4的組合……
也就是每個數字其實是獨立的，不能放在一起看，
除非我們找到一組順序，使得此子序列的對應關係合於本來的序列。
好吧，其實我不是很懂Patience sorting……
總之pile數 = lis數就對了！
那這樣要怎麼找到一組lis呢？
現在我們已經知道，每個位置能放的值了，
所以按照題目要求，我們只要從最末的值開始往前找即可。
這部份就跟O(n ^ 2)的方法是一樣的。

接著談實作，實作非常之令我苦惱……
所謂懂還不一定寫得出程式碼，就是這回事，囧。
首先要做出一個pile，所以讓seq[0]為第一個pile，
然後我們可以發現，Patience sorting其實是一個遞增數列（這應該是重點）。
也就是說，每個pile最上面的值，排在一起，一定為遞增數列。
既然是遞增，那我們可以用binary search去做search的動作。
（因為已經sort，所以可以用bin search）
兩種情況：
(1)seq[x]的值，比最後一個pile 的top值還大，就增加一個pile。
因為我們已知所有pile的top為一遞增數列，
那如果seq[x] > 最後一個pile的top值，
勢必seq[x]，大於所有pile的tope值，
所以這時候就要增加一個pile。
(2)非(1)的情況，表示seq[x] <= 最後一個pile的top值。
這時候，seq[x]這個值，可能跟前面某個pile的top值一樣，
或是介於某兩個pile值之間的情況。
如果是前者，那我們找到seq[x] == pile top時，任務就結束了。
如果是後者，那我們會得到pile[i] top < seq[x] < pile[i + 1] top。
這時，需把pile[i + 1]的top換成seq[x]才行。
如此才符合Patience sorting的第二個定義。

所以我們可以得到一種資料結構：stack包含stack，
但是實作上不用這麼麻煩，只要用stack + 取代就好了。
其實更好的作法是再用一個空間，去紀錄每個seq[x]的在lis位置，
就是紀錄他在哪個pile啦！用空間換取時間！

這樣，我們已經知道了pile數（lis長度），
也紀錄了每個seq[x]所在lis長度的位置，
那麼這題就有解了！
從最後一個seq[x]往前到seq[0]，去尋找符合lis長度的值，
找到該值後記錄下來，再把lis長度 - 1，同樣做找值的動作，
一直找到第一個lis為止。
如此，就是答案了。

另外為什麼是O(n * log(n))呢，
因為binary search是O(log(n))，
而有n個值，最慘的情況就是每個值都去做binary search，
那就會得到O(n * log(n))。

再一次感謝DJWS~
有興趣可以再看一些參考資料
wiki跟algorithmist都有。

/* ACM 481 What Goes Up
 * mythnc
 * 2012/01/16 09:58:36   
 * run time: 0.044
 */
#include <stdio.h>

#define MAXN 100000

void lis(int);
void binsearch(int, int, int);

int n;
int seq[MAXN], pos[MAXN], v[MAXN];

int main(void)
{

    n = 0;
    while (scanf("%d", &seq[n]) == 1)
        n++;

    lis(n);

    return 0;
}

/* lis: return the last max len position */
void lis(int n)
{
    int len, i, j;
    int out[MAXN];

    len = 0;
    v[len++] = seq[0];
    pos[0] = 0;

    for (i = 1; i < n; i++) {
        if (seq[i] > v[len - 1]) {
            v[len] = seq[i];
            pos[i] = len++;
        }
        else
            binsearch(0, len, i);
    }
    /* output */
    printf("%d\n-\n", len);
    for (i = n - 1, j = len - 1; i > -1 && j > -1; i--)
        if (pos[i] == j) {
            out[j] = seq[i];
            j--;
        }
    for (i = 0; i < len; i++)
        printf("%d\n", out[i]);
}

void binsearch(int begin, int end, int index)
{
    int mid;

    while (begin <= end) {
        mid = (begin + end) / 2;
        if (v[mid] == seq[index]) {
            pos[index] = mid;
            return;
        }
        else if (v[mid] > seq[index])
            end = mid - 1;
        else
            begin = mid + 1;
    }
    
    mid = (begin + end) / 2;
    if (mid == 0 && index == 1) {
        v[0] = seq[index];
        pos[index] = 0;
    }
    else {
        v[mid + 1] = seq[index];
        pos[index] = mid + 1;
    }
}