подготовка к всероссийской олимпиаде по информатике Задача 9 (16 баллов). Рассматривается последовательность, состоящая из N положительных целых чисел. Требуется вычеркнуть из последовательности наименьшее количество чисел так, чтобы оставшиеся числа шли
Подготовка к всероссийской олимпиаде по информатике
Задача 9 (16 баллов). Рассматривается последовательность, состоящая из N положительных целых чисел. Требуется вычеркнуть из последовательности наименьшее количество чисел так, чтобы оставшиеся числа шли в порядке строгого возрастания. Входные данные. Входной файл содержит целое число N (1 ≤ N ≤ 1000) – количество чисел и последовательность из N целых положительных целых чисел, каждое из которых не больше 1000. Выходные данные. В выходной файл вывести одно целое число – количество не вычеркнутых чисел.
| Примеры входных данных | Примеры выходных данных |
| 6 2 5 3 4 6 1 | 4 |
10 10 9 8 7 6 5 4 3 2 1 1
Решение задачи 9.
Язык Паскаль.
program Project_1_9;
{$APPTYPE CONSOLE}
uses SysUtils, Math;
const MAXN = 1000;
var f, g: textfile;
n, i, j, ans: integer;
a, d: array[0..MAXN-1] of integer;
begin
AssignFile(f, 'input.txt');
AssignFile(g, 'output.txt');
try
Reset(f);
4
Rewrite(g);
try
Read(f, n);
for i := 0 to n-1 do Read(f, a[i]);
for i := 0 to n-1 do
begin
d[i] := 1;
for j := 0 to i-1 do
if (a[j] < a[i]) then d[i] := max(d[i], 1 + d[j]);
end;
ans := d[0];
for i := 0 to n do ans := max(ans, d[i]);
Writeln(g, ans);
finally
CloseFile(f);
CloseFile(g);
end;
except
on EInOutError do Writeln('EInOutError!');
end;
end.
