Dãy không giảm dài nhất

[nncb2008]

Các bạn giúp mình bài toàn này nhé:Cho một dãy số nguyên (a1,a2...,an).Hãy gạch bỏ một số ít nhất các số trong dãy sao cho dãy còn lại (vẫn giữ nguyên thứ tự) là một dãy không giảm.
Không biết hàm mục tiêu như thế nào nhỉ?

[3do]

bài này dùng qui hoạch động.

f(i) = max (f(x), f(y), ...) + 1 với x, y,.. < i và ax, ay <= ai

Lưu thêm 1 số thứ để theo vết

[xera]

Giả sử có dãy a1, a2, .... , an. Bổ sung thêm MIN, MAX vào 2 đầu của dãy (MIN là 1 số đủ nhỏ, MAX là 1 số đủ lớn), như vậy, dãy không giảm dài nhất đảm bảo sẽ bắt đầu từ MIN và kết thúc tại MAX.

Ký hiệu L[i] là chiều dài dãy không giảm dài nhất bắt đầu từ a[i]. Vậy L[n+1]=1 (dãy chỉ có duy nhất phần tử MAX). Tiếp theo đi tính L[i] cho mọi i từ 1 đến n.

Giả thiết đã biết L[i+1]...L[n+1] và các dãy con tính từ a(i+1) ... a(n+1). Để thành lập dãy con dài nhất có chứa ai, cần ghép ai vào đầu dãy con nào đó bắt đầu từ ak với k trong khoảng i+1 đến n+1 mà ak>=ai và L[k] là lớn nhất.

=> L[i]=MAX(L[k])+1 với mọi i+1<=k<=n+1 và ai<=ak

Vì L[n+1] đã biết nên có thể từ đó tính ra L[n], L[n-1], ... L[0]

Lưu lại vết trong quá trình tìm ak, từ đó có thể liệt kê dãy con cần tìm. Các phần tử còn lại sẽ bị xóa.

Hình như là vậy

[nncb2008]

Xin cảm ơn, nhưng mình vẫn chưa hiểu.

[mr_invincible]

Dùng phương pháp quy hoạch động như thế này:
Gọi L[i] là độ dài dãy không giảm dài nhất mà phần tử cuối cùng là i. Như vậy thì L[i] phải là giá trị lớn nhất trong các giá trị L[j]+1 thỏa mã j<i và a[j]<=a[i] (để dãy vẫn thỏa mãn không giảm nên a[j]<=a[i] và dài nhất nên L[i]=max...)
Cuối cùng thì cần tìm giá trị lớn nhất trong các L[i] (kết quả bài toán)

[nncb2008]

Cuối cùng thì cần tìm giá trị lớn nhất trong các L[i] (kết quả bài toán)
Nhưng bài toán yêu cầu là gạch bỏ những phần tử nào trong dãy?

[mr_invincible]

Thì ngoài các số thuộc dãy không giảm đó thì gạch đi các số còn lại. Nếu muốn biết một số có thuộc dãy không thì dùng thêm 1 mảng truoc lưu các giá trị của số đứng trước số đó trong dãy không giảm dài nhất (có số cuối là số đó)