Diễn đàn tin học Nguyễn Văn Linh
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
Trang ChínhLatest imagesTìm kiếmĐăng kýĐăng Nhập

 

 Dãy con tăng dài nhất

Go down 
3 posters
Tác giảThông điệp
Hovanthong
Admin
Admin
Hovanthong


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeTue 27 Jul 2010, 13:04

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ử?
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.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
whatsgoingon
Gà nhỏ
whatsgoingon


Tổng số bài gửi : 30
Join date : 18/07/2010
Age : 29
Đến từ : Nơi tận cùng vũ trụ

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeTue 27 Jul 2010, 20:53

Bài này dùng quy hoạch động 1 cái mảng 1 chiều max[i] là độ dài dãy con lớn nhất từ a[1] tới a[i] đúng ko nhỉ, lâu rồi ko làm lại
Mà Hovanthong là ai vậy post 1 đống bài trong 1 ngày với tốc độ kinh dị chiếm hơn 1 trang luôn
Diễn đàn có thêm cái "và Hồ Văn Thông" là sao vậy, liên kết với nhàu
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeWed 28 Jul 2010, 16:36

Vói N nhỏ:
Code:

var      a,b:array[0..10000] of integer;
          i,j,jmax,n,max:integer;
 begin
 readln(n);
 for i:=1 to n do read(a[i]);
 a[n+1]:=maxint;
 b[n+1]:=1;
 for i:=n downto 1 do
 begin
 jmax:=0;
 for j:=i+1 to n do
 if (a[j]>a[i]) and (b[j]>jmax) then
 begin
 jmax:=b[j];
 end;
 b[i]:=jmax+1;
 end;
 for i:=1 to n do
 if b[i]>max then max:=b[i];
 write(max);
 end.     
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin
Hovanthong


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeWed 28 Jul 2010, 16:38

Với N lớn ta dùng tìm kiếm nhị phân.
Code:

var
n,m:longint;
a,f:array[1..30000] of longint;

function tim(x:longint):longint;
var dau,cuoi,giua:longint;
begin
if x>f[m] then exit(m+1);
if x<=f[1] then exit(1);
dau:=1;cuoi:=m;
repeat
giua:=(cuoi+dau) div 2;
if f[giua]>=x then cuoi:=giua else dau:=giua;
until cuoi-dau=1;
exit(cuoi);
end;

procedure main;
var k,i:longint;
begin
readln(n);
read(a[1]);
f[1]:=a[1];
m:=1;
for i:=2 to n do
begin
read(a[i]);
k:=tim(a[i]);
if k=m+1 then inc(m);
f[k]:=a[i];
end;
writeln(m);
end;

BEGIN
main;
END.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
whatsgoingon
Gà nhỏ
whatsgoingon


Tổng số bài gửi : 30
Join date : 18/07/2010
Age : 29
Đến từ : Nơi tận cùng vũ trụ

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeWed 28 Jul 2010, 20:41

Mình chưa bao h nghĩ tới cái áp dụng tìm kiếm nhị phân cho bài này, bạn Hovanthong giải thích thuật toán được ko
Hovanthong tham gia thảo luận luôn cho vui đi chứ, cứ thấy post toàn code thôi à, sôi nổi lên đi chứ
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeWed 28 Jul 2010, 23:16

Thuật toán của mình là quy hoạch động còn với N lớn thì dùng TKNP.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin
Hovanthong


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeWed 28 Jul 2010, 23:17

Bài này là 1 bài kinh điển.Bạn nên tự mình tìm tòi và học hỏi.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
whatsgoingon
Gà nhỏ
whatsgoingon


Tổng số bài gửi : 30
Join date : 18/07/2010
Age : 29
Đến từ : Nơi tận cùng vũ trụ

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeThu 29 Jul 2010, 07:27

À hiểu rồi, cái tìm kiếm nhị phân thì bik chỉ chưa áp dụng vào bài này thôi, thanks đã hiến thêm 1 kinh nghiệm quý báu
Về Đầu Trang Go down
littlelee
Admin
Admin
littlelee


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeThu 29 Jul 2010, 11:02

Exit(m+1), exit(1)... là chi vậy.
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeThu 29 Jul 2010, 15:28

Nếu x>f[m] thì tim:=m+1=> thoát ra.
Nếu x<=f[1] thì tim:=1=>thoát ra
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin
littlelee


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeThu 29 Jul 2010, 18:18

Hay đó. Nhưng trong TP hay BP thì ko cho cho sử dụng cái đó. ^^
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeThu 29 Jul 2010, 22:46

Bài này có thể dùng BIT nữa:
Code:

function max(a,b:ii):ii;
begin
        if a<b then  max:=b else max:=a;
end;
 
procedure up(i,x:ii);
 
begin
        while i<=n do
              begin
              t[i]:=max(t[i],x);
              i:=i+i and (-i);
              end;
end;
 
function get(i:ii):ii;
 var k:ii;
begin
        k:=0;
        while i>0 do
              begin
              k:=max(k,t[i]);
              i:=i-i and (-i);
              end;
        get:=k;
end;
 
procedure ch;
 var i,res,k:ii;
begin
            rr;
            res:=0;
            fillchar(t,sizeof(t),0);
            for i:=1 to n do
                begin
                k:=get(b[i]-1);
                res:=max(res,k+1);
                up(b[i],k+1);
                end;
            assign(f,fo);
            rewrite(f);
            write(f,res);
            close(f);
end;
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin
Hovanthong


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An

Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitimeThu 29 Jul 2010, 22:47

Code:

ii là longint.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Sponsored content





Dãy con tăng dài nhất Empty
Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Dãy con tăng dài nhất I_icon_minitime

Về Đầu Trang Go down
 
Dãy con tăng dài nhất
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Chu vi của n hình chữ nhật
» Xóa số để tạo thành số nhỏ nhất, lớn nhất.
» Dãy con dài nhất có tổng chia hết cho K
» nhập vào 2 số và tìm số nhỏ nhất ?
» Bội chung nhỏ nhất

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến