HÀNG CÂY.
Cổng vào Trung tâm thanh thiếu nhi có một hàng cây gồm N cây cảnh. Hàng cây được đánh số từ 1 đến N tính từ ngoài vào trong. Ban quản lí Trung tâm đã đo được cây thứ i có độ cao là hi. Để cho đẹp, hàng cây phải có độ cao tăng dần tính từ ngoài cổng vào (cây phía ngoài phải thấp hơn cây phía trong). Vì vậy, Ban quản lí Trung tâm quyết định chặt bỏ đi những cây có độ cao không phù hợp và giữ nguyên vị trí các cây còn lại để được một hàng cây có độ cao tăng dần.
Yêu cầu: Tìm cách loại bỏ đi một số cây sao cho số cây còn lại là nhiều nhất và hàng cây có độ cao tăng dần.
Dữ liệu vào: Cho trong file văn bản HANGCAY.INP, có cấu trúc:
- Dòng 1: Ghi số nguyên dương N, là số lượng cây ban đầu trong hàng cây (1≤N≤100)
- Dòng 2: Ghi N số nguyên dương hi (1 ≤ hi ≤ 32767) lần lượt là độ cao của cây thứ i trong hàng cây, tính từ ngoài cổng vào. Các số được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản HANGCAY.OUT, theo cấu trúc:
- Dòng 1: Ghi số nguyên dương M, là số lượng cây còn lại trong hàng cây sau khi loại bỏ.
- Dòng 2: Ghi M số nguyên dương là chỉ số của mỗi cây còn lại trong hàng cây sau khi loại bỏ. Các số phải được ghi cách nhau ít nhất một dấu cách.
Ví dụ:
|
HANGCAY.INP |
HANGCAY.OUT |
|
5 5 8 3 4 9 |
3 1 2 5 |
const fi='nix.inp';
fo='nix.out';
var
f:text;
j,i,n,max:0..100;
a,b,l,m: array [0..101] of integer;
procedure ip;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:= 1 to n do
read(f,a[i]);
close(f);
end;
procedure out;
begin
assign(f,fo);
rewrite(f);
for i:= 0 to n do
l[i] := 1;
for i:= 1 to n do
for j:= i to n do
if (a[j] > a[i] ) and (l[j] < l[i] + 1 ) then
begin
l[j] := l[i] + 1;
m[j]:= i;
end;
max:=0;
for i:= 1 to n do
if l[i] > max then
begin
j:=i;
max:=l[i];
end;
while m[j] <> 0 do
begin
l[j]:=-l[j];
j:=m[j];
end;
l[j]:=-l[j];
for i:= 1 to n do
if l[i] < 0 then write(f,i,' ');
close(f);
end;
BEGIN
ip;
out;
END.
bạn cho thêm vài ví dụ nữa đi
