//
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
Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 254,200 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: