Dãy con tăng dài nhất (bản dễ) - LCOJ: Luyện Code Online Judge

DCTDN1 - Dãy con tăng dài nhất (bản dễ)

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho một dãy số nguyên gồm ~N~ phần tử ~a_1, a_2, …, a_N~. Một dãy con đơn điệu tăng của dãy trên là dãy ~a_{i_1}, a_{i_2}, …, a_{i_k}~ sao cho: ~i_1 < i_2 < … < i_k~ và ~a_{i_1} < a_{i_2} < … < a_{i_k}~. Hãy cho biết dãy con đơn điệu tăng của dãy đã cho có nhiều nhất bao nhiêu số hạng?

Input

Dòng đầu chứa số nguyên dương ~N~;
Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, …, a_N~, mỗi số cách nhau bởi một dấu cách.

Giới hạn:

~1 ≤ n ≤ 1000, -10^9 ≤ a_i ≤ 10^9~

Output

Ghi ra độ dài của dãy con đơn điệu tăng dài nhất.

Sample

Input #1

6
1 2 5 4 6 2

Output #1

Hint

Giải thích #1:

Dãy con tăng dài nhất là dãy ~1, 2, 4, 6~ độ dài dãy này là ~4~.

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

FULL AC CHO AE THAM KHẢO

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n), dp(n + 1, 1);
    for (auto &i : a)
        cin >> i;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[j] < a[i])
            {
                dp[i] = max(1 + dp[j], dp[i]);
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end());
    return 0;
}

-3

Dinone369 đã bình luận lúc 4, Tháng 12, 2025, 14:13

include <iostream>

include <vector>

using namespace std;

int main(){ short n; cin >> n; vector<int> a(n); vector<int> L(n, 1); for (int i = 0; i < n; i++){ cin >> a[i]; } for (int i = 1; i < n; i++){ for (int j = 0; j < i; j++){ if (a[i] > a[j]){ L[i] = max(L[i], L[j]+1); } } } int maxX = L[0]; for (int i = 1; i < n; i++){ if (maxX < L[i]) maxX = L[i]; } cout << maxX; return 0; }

4

Shit đã bình luận lúc 9, Tháng 2, 2024, 7:26

day so: 1 2 5 4 5 6 Vi tri: 0 1 2 3 4 5 day so khi sort: 1 2 4 5 5 6 Vi tri khi sort: 0 1 3 2 4 5 taa thay khi sort a[i1]<a[i2] nhung vi tri lai nguoc lai vi vay ta se dem xoi

25

tri_88 đã bình luận lúc 8, Tháng 1, 2024, 8:26 ← chỉnh sửa →

Đầu tiên nhập vào một số n.

Khi nào n > 0.

Thì nhập vào 1 số a.

Tiếp theo dùng hàm lower_bound() để tìm m là vị trí phần tử đầu tiên trong multiset có giá trị lớn hơn hoặc bằng với a

Sau khi dùng hàm lower_bound() xong các bạn phải cộng thêm 1 vì vị trí m trong multiset thực tế là m+1.

Rồi kiểm tra xem nều m != multiset.end() thì xoá m đi.

(Nếu như m != multiset.end() thì xoá đi để tìm 1 vị trí khác thoả mãn)

Thì kích thước của multiset sẽ là kết quả của bài.

Code mẫu (C++) tại Đây

-2

minyzin đã bình luận lúc 13, Tháng 12, 2023, 13:51

test 6 la jz mng;-;??

0

kimbang đã bình luận lúc 27, Tháng 7, 2023, 3:29

ví dụ 5 1 7 3 4 8 thì chuỗi con dài nhất phải là 4(1,3,4,8), mà code của bạn ra 3(1,7,8)