uva 11456 - Trainsorting（dp，LIS）

題目鏈接：uva-11456,hdu-3165   題意    艾琳是個開火車的機師，她也負責車廂的調度。她喜歡把車廂依重量由大到小排列，把最重的車廂擺在火車的前方。    不幸的是，排列車廂並不容易。你不能直接把一截車廂拿起來放在別處。把一截車箱插入現有的列車中間並不切實際。一截車廂僅能接在列車的前面或後面。    車廂以事先排定的順序抵達車站。當一截車廂抵達時，艾琳可以把它接在列車的前方或後方，或根本不要這截車廂。列車越長越好，但是其中的車廂要依重量排列。    依車廂抵達的順序給你車廂的重量，艾琳所能接出的最長火車是多長？     思路    這題算是經典的類型題吧，看到這樣的就應該想到LIS。    假設第一個車廂選擇第i個放進去，那麼接下來，放在i的右邊的一定是比i的重量小的，為了讓右邊方向盡量長，    就要在序列中第i個到最後一個選最長遞減序列的順序放。    要放在i的左邊的，一定是比i的重量要大的，同理，為了讓左邊方向盡量長，應該找以i為第一個(不能讓其他代替)的最長遞增    序列。      如果用枚舉第一個車廂的樸素的方法算，並用nlogn的算法求最長遞增（減）序列，那麼復雜度達到n*n*logn    而n最大2000, 計算量達到2000*2000*11 = 4000W+,顯然超時。      所以需要轉換一下，只需要逆序計算最長遞增（減）序列，對於第i個，當它插入LIS序列時，可以得到以它為開始的最長遞增（減）    序列的長度，等於在LIS序列第一個到插入位置的個數，就是他的最長遞增（減）序列的長度了      可能沒講清楚，代碼好理解。       注意，求最長遞減序列時，我把每個數字轉化成了負數，這樣就變成了求最長遞增序列，做起來更方便。   代碼

/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source      : uva-11456 Trainsorting
 *   @description : dp, LIS
 *   @author      : shuangde
 *   @blog        : blog.csdn.net/shuangde800
 *   @email       : [email protected]
 *   Copyright (C) 2013/09/06 22:09 All rights reserved. 
 *======================================================*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 2010;
int n;
int arr[MAXN];

int main(){

    int nCase;
    scanf("%d", &nCase);
    while (nCase--) {

        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d", &arr[i]);

        vector<int>vt1, vt2;
        vector<int>::iterator iter;

        int ans = 0;

        for (int i = n - 1; i >= 0; --i) {

            int len1, len2;

            iter = lower_bound(vt1.begin(), vt1.end(), arr[i]);
            if (iter == vt1.end()) { 
                vt1.push_back(arr[i]);
                len1 = vt1.size();
            } else{
                *iter = arr[i]; 
                len1  = iter - vt1.begin() + 1;
            }

            iter = lower_bound(vt2.begin(), vt2.end(), -arr[i]);
            if (iter == vt2.end()) {
                vt2.push_back(-arr[i]);
                len2 = vt2.size();
            } else {
                *iter = -arr[i]; 
                len2 = iter - vt2.begin() + 1;
            }

            ans = max(ans, len1 + len2 - 1);
        }
        printf("%d\n", ans);
    }

    return 0;
}