Contents
Problem
題目網址
中文網址
Solution
由於可以將火車選擇皆在前方或後方,所以將原本的數列前接上顛倒的。
1 2 3 4 =>
4 3 2 1 1 2 3 4
以 2 來說它可以是在 1 前面或後面。
接著算 LIS 即可。
Code
$O(NlogL)$
UVa 11456
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
#include <vector> #include <algorithm> using namespace std;
int () { int Case, train[4000]; vector<int> lis; scanf("%d", &Case); while (Case--) { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &train[i + n]); train[n - i - 1] = train[i + n]; }
if (n) lis.push_back(train[0]);
for (int i = 1; i < (n << 1); ++i) { if (train[i] > lis.back()) lis.push_back(train[i]); else *(lower_bound(lis.begin(), lis.end(), train[i])) = train[i]; }
printf("%dn", lis.size()); lis.clear(); }
return 0; }
|
$O(N^2)$
UVa 11456
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
|
#include <cstring> #define MAX(a, b) ((a) > (b) ? (a) : (b))
int () { int Case, train[4000], len[4000]; scanf("%d", &Case); while (Case--) { int n; scanf("%d", &n); */ for (int i = 0; i < n; ++i) { scanf("%d", &train[i + n]); train[n - i - 1] = train[i + n]; }
n <<= 1; int ans = 0;
for (int i = 0; i < n; ++i) { len[i] = 1; for (int j = 0; j < i; ++j) { if (train[i] > train[j]) len[i] = MAX(len[i], len[j] + 1); } ans = MAX(ans, len[i]); }
printf("%dn", ans); }
return 0; }
|
近期评论