Uva11456 - Trainsorting (LIS)

題目大意:

有一台火車， x 輛汽車，目的是要讓火車上載滿最多汽車 (可以選擇不要加入這台汽車)，且要排序。

值得注意的是我們只能從前面或後面新增，火車是沒辦法讓我們從中間插入的，試問最多可以載幾台汽車？

分析:

naivered 大大跟天才一樣，我都沒有想到可以前後面都增加，由於數字不會重複的特性，可以這樣子使用！

舉例:

1 2 3 4 => 4 3 2 1 1 2 3 4

分解成最初狀態後則:

1 => 1
2 => 2 1 2

2 這樣子可以假設到加入前面與後面 (由於數字不會重複)

接著就算 LIS (之前我很喜歡看的演算法教學文章) 即可。

備註:

要是我寫得不好，就去看這位 naivered 大神這題的教學文，十分好理解

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL


using namespace std;


int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin);
    freopen("out.txt" , "w" , stdout);
#endif // LOCAL
    int intCase , n , intPosition ;
    string strWord , strAns , strLine ;
    vector<string> vecAns ;
    cin >> intCase ;
    n = 1 ;
    getline(cin , strLine ) ;
    getline(cin , strLine ) ;
    while(getline(cin , strLine )){
        //debug
        //cout << strLine << '\n' ;

        if(strLine != ""){
            stringstream ss ;
            ss.str("");
            ss.clear() ;
            ss << strLine ;
            intPosition = 0 ;
            strAns = "" ;
            while(ss >> strWord){
                //debug-
                //cout << strWord << '\n' ;

                if(strWord.length() > intPosition){
                    strAns += strWord[intPosition++] ;

                    //debug
                    //cout << strAns << '\n' ;

                }
            }
            vecAns.push_back(strAns) ;
        }
        else{
            cout << "Case #" << n++ << ":" << '\n' ;
            for(int i = 0 ; i < vecAns.size()-1 ; i++)
                cout << vecAns[i] << '\n' ;
            cout << vecAns[vecAns.size()-1] ;
            if(n-1 != intCase)
                cout << '\n' ;
            vecAns.clear() ;
            cout << '\n' ;
        }
    }
    return 0;
}