CFR 340 D. Bubble Sort Graph ( LIS )

Problem - 340D - Codeforces
題意：
給一個元素相異序列用以描述一個圖，所有逆序數對之間存在一條無向邊。求最大獨立集合( 集合中所有點接無邊連接 )的數量。
解法：
只要沒有逆序數對，就不會有邊。沒有逆序數對意味著是遞增序列。因此問題轉換成求 LIS。

int N;
vi A;

void init(){
    cin >> N;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

vi dp;

void preprocess(){
    dp = vi( N, INF );
    for( int i = 0; i < N; ++i )
        dp[ lower_bound( dp.begin(), dp.end(), A[ i ] ) - dp.begin() ] = A[ i ];
}

void solve(){
    cout << lower_bound( dp.begin(), dp.end(), INF ) - dp.begin() << endl;
}