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 | #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int arr[50000] = { 0 }; vector<int> dp; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &arr[i]); } dp.push_back(-1000000000); for (int i = 1; i <= n; i++) { if (dp.back() < arr[i]) { dp.push_back(arr[i]); } else { auto it = lower_bound(dp.begin(), dp.end(), arr[i]); *it = arr[i]; } } printf("%d", dp.size() - 1); } | cs |
'알고리즘 > DP' 카테고리의 다른 글
2229 조짜기 (0) | 2019.07.12 |
---|---|
2602 돌다리 건너기 (0) | 2019.07.12 |
11049 행렬 곱셈 셈 순서 (0) | 2019.07.11 |
2688 줄어들지 않아 (0) | 2019.07.10 |
9084 동전 (0) | 2019.07.09 |