let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

BEADSNB - Beads

problem.md

Biển Đà Nẵng được nhiều du khách biết đến như một trong những điểm nghỉ ngơi lý tưởng và được tạp chí Forbes (Mỹ) bình chọn là một trong những bãi biển đẹp nhất thế giới. Các bãi tắm có độ dốc lớn, nước trong xanh thích hợp cho những du khách muốn thưởng thức các loại hình dịch vụ giải trí nghỉ dưỡng, câu cá, lướt ván, lặn ngắm san hô, du thuyền,..

Trong một đợt đi du lịch ở Đà Nẵng, sáng sớm DONG3D thường đi dạo dọc bờ biển và nhặt những vỏ ốc rồi xâu chúng lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của DONG3D như sau: Ban đầu từ chuỗi rỗng, không có vỏ ốc; khi gặp một vỏ ốc mới, có thể lấy để xâu vào một trong hai đầu của chuỗi hoặc hoặc bỏ đi không lấy; cuối cùng nhận được một chuỗi vỏ ốc mà tính từ đầu chuỗi đến cuối chuỗi, các vỏ ốc có kích thước tăng dần và gồm càng nhiều vỏ ốc càng tốt.

Yêu cầu: Cho trước dãy \(a_1, a_2, \dots, a_n\) là kích thước của các vỏ ốc mà DONG3D lần lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được chuỗi gồm nhiều vỏ ốc nhất.

Dữ liệu:

  • Dòng 1 chứa số nguyên dương \(n \le 10^5\)
  • Dòng 2 chứa n số nguyên dương \(a_1, a_2, \dots, a_n (\forall i: a_i \le 10^9)\) cách nhau bởi dấu cách.

Kết quả: Ghi ra một số nguyên duy nhất là số lượng vỏ ốc trong chuỗi tạo được.

Ví dụ:

INPUT
5
4 4 5 3 1

OUTPUT
4
  • 40% số điểm ứng với các test có n ≤ 20
  • 30% số điểm ứng với các test có n thỏa mãn 20 ≤ n ≤ 1000
  • 30% số điểm ứng với các test có n thỏa mãn 1000 ≤ n ≤ 10^5
solution.md

Cần chú ý đến vỏ ốc đầu tiên được cho vào chuỗi. Giả sử chuỗi ốc đầu tiên được cho vào là \(a_i\), ta thấy dãy các vỏ được thêm vào sau cuối chuỗi sẽ tạo nên một dãy con tăng bắt đầu từ \(a_i\), còn các vỏ được thêm vào đầu chuỗi sẽ tạo nên dãy con giảm bắt đầu từ \(a_i\).

Vì vậy, ta cần tìm vị trí \(i\) mà ở đó có \(F_i + G_i - 1\) là lớn nhất, với \(F_i\) là độ dài dãy con tăng dài nhất bắt đầu từ \(a_i\), \(G_i\) là độ dài dãy con giảm dài nhất bắt đầu từ \(a_i\).

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

vector<int> longest_increasing_subsequence(vector<int> a) {
    vector<int> b(a.size()+1, INT_MAX);
    b[0] = INT_MIN;
    for (int &x: a) {
        int k = lower_bound(b.begin(), b.end(), x) - b.begin();
        b[k] = x;
        x = k;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int &x: a) cin >> x;
    reverse(a.begin(), a.end());
    auto f = longest_increasing_subsequence(a);
    for (int &x: a) x = -x;
    auto g = longest_increasing_subsequence(a);
    int res = 0;
    for (int i=0; i<n; i++) res = max(res, f[i] + g[i] - 1);
    cout << res;
    return 0;
}
Comments