Для тех, кто долго не может вкурить. Три массива dp1, dp2 и dp3. В dp1[i] рассчитываем максимальный элемент из первых i чисел. В dp2[i] - макс сумму двух элементов с расстоянием не меньше K среди первых i чисел. В dp3[i] - макс сумму трех чисел с расстоянием не меньше K среди первых i (ответ на задачу для первых i элементов). Формула перехода: dp1 просто поиск максимума. dp2: если i-й элемент взять в сумму, то оставшийся нужно брать макс из первых i-k, то есть dp1[i-k]. Если не брать iй, то ответ такой же, как на прошлом шаге. dp2[i] = max(a[i] + dp1[i-k], dp2[i-1]) - берем лучший вариант. dp3: аналогично. Если берем iй в тройку, то остальные два нужно брать оптимально, как раз dp2[i - k]. Если не берем - ответ не меняется с предыдщуего шага. Итого dp3[i] = max( dp3[i - 1], a[i] + dp2[i-k] ). Можно заметить, что хранить все массивы не нужно, достаточно поддерживать только dp1[i-2k], dp2[i-k], dp3[i] и предыдущие значения каждого массива. Получится как раз решение из видео. Но ИМХО, классическим подходом динамики объяснять (и особенно понимать!) проще
Здравствуйте Иван Викторович, смотрю вас давно, после того как начал готовиться к ОГЭ, можно после того как закончите этот плейлист, сделаете разбор всех тип задач 1 задания, 2 и так далее, спасибо большое за то что вы есть...
Как по мне, если и делать так, то только со сложными задачами, ведь какой смысл разбирать например первое или четвёртое задание, если они идентичны и очень просты
@@Doule_XP ну да, согласен, но во втором задание есть и сложные типы, где сложный подбор, я просто до сих пор не врубился, там может быть 4 строки, а у тебя в таблице три
А мне не очень понятно, почему мы взяли цикл фор с k*2. Если это позволяет как-то сократить время работы программы, то объясните пожалуйста, почему и как это работает
@@user-yq2ky3bv3l, но ведь это не так Можно чтобы это расстояние оказалось и больше чем 2k Например если k =3 то тройка элементов с индексами 1; 100 и 1000 нам тоже подходит Как здесь рассматривается такой случай?
@@jakeendless как я поняла, i принимает значение от k*2 до n, это значит, что мы перебираем значения i от минимально возможного, так, чтобы числа подходили под условие, до n, в котором также выполняются условия задачи, дальше в поисках каждого отдельного максимума перебираются отдельные значения, всё также от минимально возможного до максимально возможного, например, число k = 2, всего чисел n = 10, в таком случае i пройдёт по значениям от 4 до 10, спускаемся в первый максимум, тут перебираются значения i, которые изначально больше 2*k, отнимая от i число 2*k будем получать значения индексов от 0 до 6, по индексам ищем первый максимум, далее идём в во второй максимум, тут уже будут значения индексов от 2 до 8, также находим максимальную сумму 2 чисел, в третьем максимуме теперь уже сумма всех 3 чисел В условии задачи говориться, что между любыми 2 числами должен быть промежуток k и больше, значит, какие числа не возьми, в любом случае промежуток между ними должен быть k и больше, поэтому перебираемся от наименьшего возможного расстояния от начала списка, то есть 2k, это минимальный промежуток, в который можно вместить 3 числа и между ними будет ровно k, дальше при итерации расстояние будет всё больше, поэтому и случай, когда больше k расстояние тоже учитывается, всё это делается потому что ищем мы максимумы, которые не зависят друг от друга, поэтому достаточно лишь условие, что между ними промежуток как минимум k, дольше они сами по себе могут быть и больше, но не меньше k
Потому что у нас есть три идущих друг за другом числа, расстояние между каждыми двумя К, значит расстояние между крайними 2*К. В коде i - это третье число, i-k - второе и i-2k - первое
Чтобы ученик не мог тупо перебрать все значения файла и быстро найти ответ. Обычно, файл Б проверяет умение ученика придумывать и реализовывать разного рода алгортмы для эффективного решения
Иван Викторович, можете объяснить, почему в 24 задании мы открываем файл кодом s = open ('*'), а в 27 задании уже with open ('*') as f? В чём разница между этими двумя строками? Заранее спасибо
легко написано и круто, у всех ютюберов это решение, а кто его придумал не понятно... я долго с ним сидел, сам пытался...но тут прям круто сделано на Max ах
Файлы к варианту: doc.fipi.ru/ege/demoversii-specifikacii-kodifikatory/2024/inf_11_2024.zip
Для тех, кто долго не может вкурить.
Три массива dp1, dp2 и dp3. В dp1[i] рассчитываем максимальный элемент из первых i чисел. В dp2[i] - макс сумму двух элементов с расстоянием не меньше K среди первых i чисел. В dp3[i] - макс сумму трех чисел с расстоянием не меньше K среди первых i (ответ на задачу для первых i элементов).
Формула перехода:
dp1 просто поиск максимума.
dp2: если i-й элемент взять в сумму, то оставшийся нужно брать макс из первых i-k, то есть dp1[i-k]. Если не брать iй, то ответ такой же, как на прошлом шаге. dp2[i] = max(a[i] + dp1[i-k], dp2[i-1]) - берем лучший вариант.
dp3: аналогично. Если берем iй в тройку, то остальные два нужно брать оптимально, как раз dp2[i - k]. Если не берем - ответ не меняется с предыдщуего шага. Итого
dp3[i] = max( dp3[i - 1], a[i] + dp2[i-k] ).
Можно заметить, что хранить все массивы не нужно, достаточно поддерживать только dp1[i-2k], dp2[i-k], dp3[i] и предыдущие значения каждого массива. Получится как раз решение из видео.
Но ИМХО, классическим подходом динамики объяснять (и особенно понимать!) проще
спасибо за разбор всей демо)👍
Спасибо!
спасибо за простой разбор сложного задания
так держать
спасибо
А как узнать из каких чисел сложился ответ и номера этих чисел в списке?
супер
Здравствуйте Иван Викторович, смотрю вас давно, после того как начал готовиться к ОГЭ, можно после того как закончите этот плейлист, сделаете разбор всех тип задач 1 задания, 2 и так далее, спасибо большое за то что вы есть...
Как по мне, если и делать так, то только со сложными задачами, ведь какой смысл разбирать например первое или четвёртое задание, если они идентичны и очень просты
@@Doule_XP ну да, согласен, но во втором задание есть и сложные типы, где сложный подбор, я просто до сих пор не врубился, там может быть 4 строки, а у тебя в таблице три
@@MrSasuke1337 там если столбиков больше чем надо, то где то ошибка, может быть функцию неправильно написал, если ты про это
Все правильно там, там надо самому подбирать, серое вещество включать надо, а у меня не получается так думать сверхъестественно
А мне не очень понятно, почему мы взяли цикл фор с k*2. Если это позволяет как-то сократить время работы программы, то объясните пожалуйста, почему и как это работает
Нам нужно, чтобы между любыми двумя числами прошло не менее k минут, значит между тремя числами должно пройти 2k
минут
@@user-yq2ky3bv3l, но ведь это не так
Можно чтобы это расстояние оказалось и больше чем 2k
Например если k =3 то тройка элементов с индексами 1; 100 и 1000 нам тоже подходит
Как здесь рассматривается такой случай?
@@user-yq2ky3bv3lесли бы там между элементами тройки расстояние было бы ровно k, то я понял код, но тут же не менее
@@jakeendless как я поняла, i принимает значение от k*2 до n, это значит, что мы перебираем значения i от минимально возможного, так, чтобы числа подходили под условие, до n, в котором также выполняются условия задачи, дальше в поисках каждого отдельного максимума перебираются отдельные значения, всё также от минимально возможного до максимально возможного, например, число k = 2, всего чисел n = 10, в таком случае i пройдёт по значениям от 4 до 10, спускаемся в первый максимум, тут перебираются значения i, которые изначально больше 2*k, отнимая от i число 2*k будем получать значения индексов от 0 до 6, по индексам ищем первый максимум, далее идём в во второй максимум, тут уже будут значения индексов от 2 до 8, также находим максимальную сумму 2 чисел, в третьем максимуме теперь уже сумма всех 3 чисел
В условии задачи говориться, что между любыми 2 числами должен быть промежуток k и больше, значит, какие числа не возьми, в любом случае промежуток между ними должен быть k и больше, поэтому перебираемся от наименьшего возможного расстояния от начала списка, то есть 2k, это минимальный промежуток, в который можно вместить 3 числа и между ними будет ровно k, дальше при итерации расстояние будет всё больше, поэтому и случай, когда больше k расстояние тоже учитывается, всё это делается потому что ищем мы максимумы, которые не зависят друг от друга, поэтому достаточно лишь условие, что между ними промежуток как минимум k, дольше они сами по себе могут быть и больше, но не меньше k
почему мы смотрим только элементы, расстояние между которыми К? в условии же сказано, что расстояние не менее К, а значит может быть больше
Тогда будет не максимальная сумма
Добрый день! объясните, пожалуйста, доступно: почему при поиске от первого найденного до второго мы берём именно коэффициент 2 перед K ?
Потому что у нас есть три идущих друг за другом числа, расстояние между каждыми двумя К, значит расстояние между крайними 2*К. В коде i - это третье число, i-k - второе и i-2k - первое
почему K*2?
Идеально! Интересно почему файл А гораздо больше чем Б?
Чтобы ученик не мог тупо перебрать все значения файла и быстро найти ответ. Обычно, файл Б проверяет умение ученика придумывать и реализовывать разного рода алгортмы для эффективного решения
Имба
Иван Викторович, можете объяснить, почему в 24 задании мы открываем файл кодом s = open ('*'), а в 27 задании уже with open ('*') as f? В чём разница между этими двумя строками? Заранее спасибо
открывает файл функция open, просто в 27 я еще использовать контекстный менеджер with. А так можно было и без него
with просто сам закрывает файл, не надо f.close() писать
ACPI BIOS ERROR выдает это,как чинить ноут
биос устарел
@@dvxv4016 он новый был,но его уже заменили, оказался брак
Автор топ
подозрительно лёгкое 27-ое попалось в демке..
Не жди такого на ЕГЭ)
ловушка будет
легко написано и круто, у всех ютюберов это решение, а кто его придумал не понятно... я долго с ним сидел, сам пытался...но тут прям круто сделано на Max ах