UVa 11456. Trainsorting

Description

Erin是一個開火車工程師。他喜歡把車廂按照其重量來安排，重的車廂排在前端。
不幸的是，把車廂排序並不是一件容易的事。你只能將一節車廂加在一列火車的前端或後端。
各個車廂來到火車站的順序及其重量是已經知道的。當每節車廂來到的時候，Erin可以把它加到火車的兩端，或者不加進去。最後，火車的總車廂數是越長越好，不過要記得車廂得按照重量大小排列。
給你按照出現順序各車廂的重量，Erin最長可安排車廂的長度是多少？

Input Format

輸入的第一列有一個整數表示測試資料的組數。
每組資料的第一列會有1個整數$n$ ,$(0 \le n \le 2000)$，代表車廂的數目。接下來$n$列整數，每列有一個大於等於0的整數，代表各車廂的重量。
請注意：所有車廂的重量都不一樣。請參考 Sample Input。

Output Format

對每組測試資料，Erin最長可安排車廂的長度是多少。

Sample Input

1
3
1
2
3

Sample Output

3

UVa - 11456
翻譯來源：Luckycat

Solution

因為有選取或不選取，可以考慮到使用DP的方法解。
令$up[i]\ down[i]$代表重量 大於/小於 第$i$車廂的最大車廂數。
接著跑迴圈每次取$max(ans, up[i] + down[i]-1)$就可以得到答案了。

Code

/*************************************************************************
  > File Name: 11456 - Trainsorting.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Sat May 19 14:10:47 2018
*************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int up[2002], down[2002];
int input[2003];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int c, n;
    cin >> c;
    while(c--) {
        cin >> n;
        for (int i = n; i; i--)
            cin >> input[i];
        int ans = 0;
        for (int i = 1; i <= n; i++) up[i] = down[i] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (input[j] < input[i])
                    up[i] = max(up[i], up[j] + 1);
                else
                    down[i] = max(down[i], down[j] + 1);
            }
            ans = max(ans, up[i] + down[i] - 1);
        }
        cout << ans << '\n';
    }
    return 0;
}