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

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Hovanthong
Admin
Admin


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

Bài gửiTiêu đề: Dãy con tăng dài nhất   Tue 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ỏ


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

Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Tue 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


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

Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Wed 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.     

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin


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

Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Wed 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.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
whatsgoingon
Gà nhỏ


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

Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Wed 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


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

Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Wed 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.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin


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

Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Wed 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.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
whatsgoingon
Gà nhỏ


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

Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Thu 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


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

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

Exit(m+1), exit(1)... là chi vậy.

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


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

Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Thu 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

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


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

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

Hay đó. Nhưng trong TP hay BP thì ko cho cho sử dụng cái đó. ^^

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


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

Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Thu 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;

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Hovanthong
Admin
Admin


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

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

Code:

ii là longint.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Sponsored content




Bài gửiTiêu đề: Re: Dãy con tăng dài nhất   Today at 18:47

Về Đầu Trang Go down
 
Dãy con tăng dài nhất
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

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