Задача 9. Исправление успеваемости (вручную). Как вы наверняка знаете, Вовочка не является примерным учеником. За учебный год н получил много разных отметок, и теперь не знает, как показать дневник своему тцу. Отец Вовочки считает хорошими отметки 6 и выше, а все остальные считает лохими. Дело в том, что Вовочке было обещано лишить его отдыха в Летней школе по информатике в том случае, если он когда-либо получит три или более плохие отметки подряд.
Вовочка уже давно научился стирать отметки из дневника, но с каждой стертой отметкой вероятность раскрытия такой секретной операции возрастает. В настоящий момент перед ним стоит непростая задача удалить наименьшее -
количество отметок из имеющейся последовательности так, чтобы после удаления никакие три плохие отметки не шли подряд. Помогите Вовочке решить задачу и подарить ему шанс участия в летней школе по
информатике. Программа получает на вход в первой строке целое число n (1 << n < 5000), где п
количество отметок, полученных Вовочкой за год. Вторая строка содержит последовательность целых чисел от 1 до 10. Отметки заданы в хронологическом порядке.
В первую строку выведите - наименьшее количество отметок, которые надо удалить из последовательности.
Во вторую строку выведите последовательность отметок, которая получается после оптимального исправления успеваемости. Если возможных оптимальных решений несколько выведите любое.
Паскаль абц
Ответы
Ответ:Для решения данной задачи требуется использовать жадный алгоритм.
Алгоритм:
Считываем число n - количество отметок.
Считываем последовательность отметок и записываем её в массив.
Создаем массив dp длиной n+1, в котором будем хранить количество отметок, которые нужно удалить до i-й отметки (0 <= i <= n).
Инициализируем dp[0] = 0 и dp[1] = 0.
Для каждой i-й отметки (2 <= i <= n) рассматриваем два варианта:
5.1. Оставляем i-ю отметку. Тогда, если i-я отметка хорошая (больше или равна 6), dp[i] = dp[i-1], иначе dp[i] = dp[i-1] + 1.
5.2. Удаляем i-ю отметку. Тогда dp[i] = dp[i-2] + 1, если i-1-я и i-я отметки плохие, и dp[i] = dp[i-2], если i-1-я отметка плохая, а i-я хорошая или наоборот.
Находим минимальное значение dp[n].
Создаем новый массив res длиной n-min, в котором будем хранить последовательность отметок, полученную после оптимального исправления успеваемости.
Проходим от конца массива dp до начала и восстанавливаем последовательность отметок, добавляя каждую i-ю отметку в res, если dp[i] не равно dp[i-1].
Выводим минимальное количество удаленных отметок и полученную последовательность отметок.
Пример кода на Pascal:
var
n, i, j, min, count: integer;
marks, dp, res: array of integer;
begin
readln(n);
setlength(marks, n);
for i := 0 to n - 1 do
read(marks[i]);
setlength(dp, n + 1);
dp[0] := 0;
dp[1] := 0;
for i := 2 to n do
begin
if marks[i - 1] >= 6 then
dp[i] := dp[i - 1]
else
dp[i] := dp[i - 1] + 1;
if (i >= 3) and (marks[i - 1] < 6) and (marks[i - 2] < 6) and (dp[i] > dp[i - 2] + 1) then
dp[i] := dp[i - 2] + 1;
if (i >= 3) and ((marks[i - 1] >= 6) xor (marks[i - 2] >= 6)) and (dp[i] > dp[i - 2]) then
dp[i] := dp[i - 2];
end
Объяснение: