//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Chia dãy

 

Dãy số M phần tử B được gọi là dãy con của dãy số A gồm N phần tử nếu tồn tại một mã chuyển C gồm M phần tử thoả mãn B[i]=A[C[i]] với mọi I = 1…M và 1 ≤ C[1] < C[2] < … < C[m] ≤ N.

Một cách chia dãy A thành các dãy con “được chấp nhận” nếu các dãy con này là các dãy không giảm và mỗi phần tử của dãy A thuộc đúng một dãy con.

MH được yêu cầu phải chia dãy con ban đầu thành ít dãy con nhất mà vẫn “được chấp nhận”. Bạn hãy giúp MH tìm số dãy con ít nhất trong phương án chia tối ưu nhé !!!

InputDIVSEQ.INP

  • Dòng đầu tiên ghi số N là số phần tử của dãy A.
  • N dòng tiếp theo ghi N số tự nhiên là các phần tử của dãy A.

Output:            DIVSEQ.OUT

  • Ghi một duy nhất là số lượng dãy con ít nhất thỏa mãn.

Giới hạn:

  • N ≤ 105
  • Ai ≤ 109
  • Thời gian: 1 s/test
  • Bộ nhớ: 2MB

Ví dụ:

DIVSEQ.INP DIVSEQ.OUT
4

1

5

4

6

2

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: