[Đà Nẵng - TST - 2024] Bài 1: Cắt dãy số

Xem dạng PDF
Gửi bài giải
Điểm: 50,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Người đăng:
clue_
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Cho một xâu ~S~ có độ dài ~n~ chỉ gồm các ký tự số. Hãy tìm cách cắt xâu ~S~ thành các đoạn liên tiếp nhau khác rỗng để tạo thành một dãy số (trong đó mỗi đoạn con tương ứng một số và số này có thể chứa số 0 ở đầu) sao cho độ dài của dãy con không giảm của dãy số đó là lớn nhất.

  • Đoạn con liên tiếp là đoạn con thu được bằng cách xoá đi một số phần tử ở đầu và cuối xâu (có thể là không xoá phần tử nào).
  • Dãy con tăng không giảm có độ dài lớn nhất là khi ta xoá đi một số phần tử của dãy ban đầu thì phần thu được sẽ là một dãy không giảm và có độ dài lớn nhất.

Yêu cầu: Tìm độ dài dãy con không giảm dài nhất sau khi cắt xâu.

Input

  • Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 2 \times 10^3~).
  • Dòng tiếp theo chứa xâu ~S~ gồm ~n~ kí tự.

Output

  • Ghi ra độ dài dãy con không giảm dài nhất.

Sample Input 1

8
13220131

Sample Output 1

4

Bình luận

Hãy đọc nội quy trước khi bình luận.