CTDL và giải thuật - Giải thuật Qui hoạch động
Một dãy không giảm là dãy mà các phần tử sau không nhỏ hơn các phần tử trước.
Nhập vào số nguyên dương n
và một dãy số nguyên a
. Hãy xóa một số phần tử trong dãy a để dãy trở thành dãy không giảm dài nhất có thể. Nếu có nhiều cách xóa mà dãy còn lại xuất hiện sớm hơn. In dãy còn lại ra màn hình, sau mỗi phần tử có đúng một khoảng trắng.
Ví dụ:
- Test mẫu 1:
Input Output 8
1 4 2 1 4 6 2 71 4 4 6 7
Vớia = [1, 4, 2, 1, 4, 6, 2, 7]
thì kết quả mong muốn là"1 4 4 6 7 "
.
- Test mẫu 2:
Input Output 3
3 2 13
Vớia = [3, 2, 1]
thì kết quả mong muốn là"3 "
.
Hướng dẫn bài tập.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
int a[10001], b[10001], t[10001], kq[10001];
int main(){
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
for (int i = 0; i < n; i++){
b[i] = 1;
}
for (int i = 1; i < n; i++){
for (int j = 0; j < i; j++){
if (a[i] >= a[j] && b[j] + 1 > b[i]){
b[i] = b[j] + 1;
t[i] = j;
}
}
}
int csMax = 0;
for (int i = 1; i < n; i++){
if (b[csMax] < b[i]){
csMax = i;
}
}
int k = b[csMax];
for (int i = k-1; i >= 0; i--){
kq[i] = a[csMax];
csMax = t[csMax];
}
for (int i = 0; i < k; i++){
cout << kq[i] << " ";
}
return 0;
}