Đề bài:
Thuật toán:
- Rời rạc hóa lại dãy
- Gọi F[i] là độ dài dãy con tăng dài nhất kết thúc là số <= i
- F[i] = max(F[1..a[i]-1] + 1)
- Sử dụng cấu trúc dữ liệu BIT để tính mảng F trong O(logn)
- ĐPT: O(nlogn)
Code:
using namespace std; //#include<bits/stdc++.h> #include <algorithm> #include <stdio.h> #define FOR(i,a,b) for (long long i=a;i<b;i++) #define FORE(i,a,b) for (long long i=a;i<=b;i++) #define FORD(i,a,b) for (long long i=a;i>=b; i--) int n, a[300010], T[300010], c[300010], f[300010], dem; pair<int, int> b[300010]; int Get(int x) { int ans = 0; if (x == 0) return 0; while (x > 0) { ans = max(ans, T[x]); x -= x & (-x); } return ans; } void Update(int x, int v) { while (x <= n){ T[x] = max(T[x], v); x += x & (-x); } } int main() { //freopen("LIS.inp", "r", stdin); //freopen("LIS.out", "w", stdout); //cin>>n; scanf("%d", &n); FORE(i, 1, n) { //cin>>a[i]; scanf("%d", &a[i]); b[i].first = a[i]; b[i].second = i; } sort(b + 1, b + n + 1); int dem = 1; c[ b[1].second ] = dem; FORE(i, 2, n) { if (b[i].first > b[i - 1].first) dem++; c[ b[i].second ] = dem; } int ans = 0; FORE(i, 1, n) a[i] = c[i]; //FORE(i, 1, n) cout<<a[i]<<" ";cout<<"=="<<endl; //cout<<"????"<<endl; FORE(i, 1, n) { f[i] = Get(a[i] - 1) + 1; Update(a[i], f[i]); ans = max(ans, f[i]); } //cout<<ans<<endl; printf("%d", ans); return 0; } |
Speak Your Mind