| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
QBDIVSEQ - 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.
Yêu cầu: Bạn hãy chia dãy con ban đầu thành ít dãy con nhất mà vẫn "được chấp nhận".
Input
Dòng đầu tiên ghi số N là số phần tử của dãy A. ( N ≤ 105 )
N dòng tiếp theo ghi N số tự nhiên là các phần tử của dãy A. ( Ai ≤ 109 )
Output
Ghi một duy nhất là số lượng dãy con ít nhất thỏa mãn.
Example
Input: 4 1 5 4 6 Output: 2
| Được gửi lên bởi: | special_one |
| Ngày: | 2008-12-10 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
| Nguồn bài: | Ioicamp - Marathon 06 - 07 |
hide comments
|
||||||
|
2021-05-27 18:03:14
Tham khảo: https://vnspoj.github.io/problems/QBDIVSEQ |
||||||
|
2021-03-22 16:32:24
hay |
||||||
|
2020-09-27 16:47:18
Trâu cũng AC |
||||||
|
2020-07-27 03:43:18
cần gì tìm dãy con giảm đâu nhỉ :v |
||||||
|
2020-02-16 14:18:47
mọi người đừng có spoil cách làm nhé |
||||||
|
2019-10-04 04:58:14
bài hay! |
||||||
|
2019-09-06 07:19:29
peo u nu |
||||||
|
2019-03-28 12:35:39
đề hay! |
||||||
|
2019-01-03 17:37:19
Cho bài toán: Dãy A gồm n phần tử, hãy chia dãy thành các dãy tăng dần sao cho chia ít dãy nhất... Answer : Tìm dãy con giảm dài nhất ! |
||||||
|
2017-10-04 09:36:57
Code AC: http://123link.top/QBDIVSEQ |
||||||
RSS