Nội dung Bài tập
- Mã:
- DHLTNC_CT3_N7_ChatNhiPhan_1
- Tên:
- Chặt nhị phân B1
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4801103093
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".
Dữ liệu: Vào từ file văn bản QBDIVSEQ.INP
+ 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)
Kết quả: Ghi ra file văn bản QBDIVSEQ.OUT một duy nhất là số lượng dãy con ít nhất thỏa mãn.
Input | Output |
4 1 5 4 6 | 2 |
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
LTNC - ÔN TẬP LỚP THẦY THƯ 
#include <bits/stdc++.h>using namespace std;bool check(int x) { if(x==2 || x==3) ret...