Задача "Возрастающая последовательность", требуется помощь в решении Опции

[neZvezda]

Остался последний курсовик.
Вот задача из него:

Даны n целых чисел Х1, X2,...Xn.
Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

Ограничения:1<=n<=10 000; 1<=Xi<=60 000, время 4с.

Ввод из файла incseq.in. В первой строке находится число n. В следующей строке находятся n чисел через пробел.

Вывод в файл incseq.out. В первой строке выводится количество невычеркнутых чисел, во второй-сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.

ПРИМЕР
Ввод
6
253461

Вывод
4
2346

И сравнивать следует 3 соседних числа, и если последующее больше предыдущего, то вычеркивается последующее? Или по 2 сравнивать?
Запуталась совершенно.

Сообщение отредактировано: neZvezda - 8.11.2005 20:41

[volvo]

To: neZvezda
http://algolist.manual.ru/olimp/rec_prb.php (Задача №20)

[neZvezda]

Здесь присутствует такая вещь, как разрыв последовательности. А он мне не нужен и программой не предусмотрен, как я поняла. Тогда его выкидыыввать?
И что делать с файлами? Тут же ввод и вывод в файл идет. А программ все делает в окне паскаля. =(

const max=100; {max dlina massiva A} 
var
sw,l,i,j,k,n,m,maxind,swind:integer;
c:array [0..max,1..max] of integer;
x,y:array [1..max,1..max] of integer;
a,b:array [1..max] of integer;
begin
Write('Vvedite N:');
readln(n);
Writeln('Vvedite posledovatelnost');
for i:=1 to n do
read(a[i]);
readln;
Write('Vvedite kol-vo razrivov posledovatelnosti:');
readln(m);
fillchar(c,sizeof©,0); {zanylenie с, x и y} fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
for i:=1 to m+1 do
for j:=n downto 1 do
begin
c[i,j]:=1;
for k:=j+1 to n do
if (a[k]>a[j]) and (c[i,k]>=c[i,j]) then
begin
c[i,j]:=c[i,k]+1;
x[i,j]:=k;
y[i,j]:=i;
end;
for k:=j+1 to n do
if c[i-1,k]>=c[i,j] then
begin
c[i,j]:=c[i-1,k]+1;
x[i,j]:=k;
y[i,j]:=i-1;
end;
end;
maxind:=1;
for i:=1 to n do
if c[m+1,i]>c[m+1,maxind] then
maxind:=i;
l:=c[m+1,maxind];
j:=maxind;i:=m+1;k:=1;
while (c[i,j]<>1) do
begin
b[k]:=j;  {v massiv b vipisivaem indeksi elementov} inc(k); 
 {максимальной по длине подпоследователь}
sw:=x[i,j]; {ности в прямом порядке}
i:=y[i,j];
j:=sw;
end;
b[k]:=j;
for i:=1 to k do write(a[b[i]],' ');
writeln;
writeln('Dlina=',l);
end.

.

[volvo]

To: neZvezda
А ты ходила по ссылке, которую я дал? Внимательно читала, что там написано? Там даже программа приведена (после небольшой корректировки вот что получилось):

const _max = 100;
var
  a, b, c: array[1 .. _max] of integer;
  n, i, j: integer;
  indexmax, max: integer;
begin
  write('n = '); readln(n);
  for i := 1 to n do
    readln(a[i]);

  for i:=2 to N do
    B[i]:=0;

  C[1]:=0;
  B[1]:=1;
  Max:=1;
  IndexMax:=1;
  
  for i:=2 to N do
    for j:=1 to i-1 do
      if (A[j]<A[i]) AND (B[i]<B[j]+1) then begin
        C[i]:=j;
        B[i]:=B[j]+1;
        if B[i]>Max then begin
          Max:=B[i];
          IndexMax:=i
        end;
      end;
  
      while IndexMax<>0 do begin
        write(A[IndexMax], ' ');
        IndexMax:=C[IndexMax]
      end;
  
end.

Единственное, что остается сделать - это "развернуть" вывод (в этой программе полученная последовательность печатается от конца к началу) и направить вывод в файл. И всё !

Я надеюсь, с разворотом последовательности проблем НЕ возникнет? И с выводом в файл их тоже не должно быть...

[neZvezda]

volvo, спасибо
Сейчас попробую развернуть.