LIQ spoj – Dãy con tăng dài nhất
Nguồn đề bài: http://vn.spoj.com/problems/LIQ/ 1. Đề bài LIQ Dãy con tăng dài nhất Cho một dãy số nguyên gồm N phần tử A[1], A[2], … A[N]. Biết rằng dãy con tăng đơn điệu là 1 dãy A[i 1 ],… A[i k ] thỏa mãn i 1 < i 2 < … < i k và A[i 1 ] < ...
Nguồn đề bài: http://vn.spoj.com/problems/LIQ/
1. Đề bài LIQ Dãy con tăng dài nhất
Cho một dãy số nguyên gồm N phần tử A[1], A[2], … A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i1],… A[ik] thỏa mãn
i1 < i2 < … < ik và A[i1] < A[i2] < .. < A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?
Download test và solution (C/C++, Pascal) tại đây.
Input
- Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000).
- Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).
Output
Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Ví dụ
Input:
6
1 2 5 4 6 2
Output:
4
Giải thích test ví dụ: Dãy con dài nhất là dãy A[1] = 1 < A[2] = 2 < A[4] = 4 < A[5] = 6, độ dài dãy này là 4.
Gợi ý: Sử dụng phương pháp Quy Hoạch Động. F[i]: Độ dài dãy con đơn điệu tăng dài nhất mà phần tử cuối cùng là số A[i] này.
2. Hướng dẫn LIQ SPOJ Dãy con tăng dài nhất
– Gọi F[i] là độ dài dãy con tăng dần dài nhất kết thúc tại i
– khởi tạo F[i]=1; (với i=1..n)
– F[i]=max(F[i],F[j]+1) (A[i]>A[j] ; i=1..n, j=1..i-1).
– nghiệm bài toán Max(F[i]) (i=1..n)
3. Code tham khảo LIQ SPOJ Dãy con tăng dài nhất
a. Code Pascal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | const fi='; nmax=1000; type data=longint; var f:text; A,B:array[0..nmax+1] of data; n:data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do read(f,a[i]); close(f); end; function max(a,b:data):data; begin if a>b then exit(a); exit(b); end; procedure qhd; var i,j,res:data; begin res:=1; for i:=1 to n do begin b[i]:=1; for j:=1 to i-1 do if A[i]>a[j] then b[i]:=max(b[i],b[j]+1); res:=max(res,b[i]); end; writeln(res); end; begin docfile; qhd; end. |
b. code c++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <stdio.h> #include <algorithm> using namespace std; #define nmax=1000 int n; int a[1000], f[1000]; int main() { scanf("%d",&n); int i,j; for (i=1; i<=n; i++) { scanf("%d",&a[i]); f[i]=1; } for (i=1; i<=n; i++) { for (j=i+1; j<=n; j++) { if (a[i]<a[j]) f[j]=max(f[i]+1,f[j]); } } int res=0; for (i=1; i<=n; i++) res=max(res,f[i]); printf("%d",res); return 0; } |
