PDA

View Full Version : [help] cần người test bài



MMKC_IT
08-03-2008, 22:36
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

Mình lam thế này không bít sao chỗ nào mà bị chấm 0 điểm


program day_con_tang;

var max,n,dem:integer;
a:array[1..1000] of integer;


procedure input;
var i:integer;

begin
readln(n);
for i:=1 to n do readln(a[i]);
end;

procedure output;
var i,j,dem,so:integer;
begin
so:=0;
if n>2 then
begin
for i:=1 to (n-1) do
begin
dem:=1;
for j:=(i+1) to n do
begin
if so<a[j] then inc(dem);
so:=a[j];
end;
if max<dem then max:=dem;
end;
end
else write(n);
end;
begin

input;
output;
if n>2 then
write(max);

end.

nncb2008
09-03-2008, 01:06
Đây là một bài quy hoạch động, bạn giải như trên tôi không rõ thuật toán của bạn như thế nào nên khó nhận xét lắm. Bạn mô tả rõ thêm được không?
Tôi nghĩ ít ra cũng được điểm phần input.

MMKC_IT
09-03-2008, 11:42
thì tư tưởng của mình là : xét từ số thứ 1 -> n nếu a[i]<a[i+1] thì mình tăng biến đếm lên. Khi xét xong mình xem biến đếm có lơn hơn mã không, nếu lớn thì mã:=dem, sau đó mình xét đến số thứ 2

mr_invincible
11-03-2008, 21:33
Hình như bạn này đang làm mấy bài trên SPOJ thì phải, hết bài điền số vào vòng tròn đến bài này :D

tastsuka
11-03-2008, 23:06
với cách làm trên chỉ tìm ra dãy con tăng đơn điệu liên tiếp dai nhât thôi
tức là tìm ra dãy a[i], a[i+1], a[i+2],...a[i+k] chứ ko phải là dãy tăng đơn điệu dài nhất. Đây là một bài qhd cơ bản thôi mà