Привет всем, сегодняшняя тема codeforces — это вопрос С конкурса образования.
Обучение — это особое мероприятие codeforces, его основная функция — обучать, то есть давать возможность большему количеству людей понять механизм соревнования codeforces. Поэтому вопросы образования олимпиад будут относительно легкими.Больше подходит для начинающих. Хотя этот вопрос, который я выбрал, называется вопросом C, он не очень сложный и очень простой.
Ссылка: https://codeforces.com/contest/1418/problem/C
Этот вопрос прошли более 3600 человек, что меньше, чем вопросы, введенные ранее, но сложность вопроса на самом деле ниже. Давайте поговорим о теме без лишних слов.
смысл названия
Смысл этого вопроса тоже очень интересный, а предыстория тоже игровая. Говорят, что однажды вы с друзьями вместе играете дома в игру, в которой всего n боссов. Эти боссы имеют разные уровни сложности, некоторые из них легкие, а некоторые сложные. Ваша техника лучше, чем у вашего друга. Вы двое по очереди сражаетесь с боссом.
В игре оговаривается, что каждый раз можно играть как минимум с одним боссом, и максимум можно играть с двумя боссами. Поскольку ваша сила лучше, вы можете победить всех боссов. Тем не менее, ваши основные друзья относительно хороши, и вы можете победить только простых боссов, Если вы встретите босса в сложном режиме, вы можете получить только золото. Деньги дружбы тоже деньги, ты надеешьсяСвести к минимуму криптонитЗавершите игру на предпосылке. Теперь, когда известна сложность всех боссов и друзья с базы начинают игру первыми, сколько раз требуется минимальное количество криптонового золота в соответствии с лучшей стратегией?
Образец
Сначала дается число t, которое представляет количество групп тестовых данных. Для каждого набора данных дается число n, которое представляет количество боссов. Затем даны n целых чисел от 0 до 1, 0 означает, что босс находится в легком режиме, 1 означает сложный режим. Попросите вернуть число, то есть минимальное количество криптонового золота. в
input:
8
1 0 1 1 0 1 1 1
output:
2
Джию сначала убивает двух боссов, 1 и 2, за криптоновое золото один раз.
"Я" убил боссов 3 и 4
Друг убивает босса 5
"Я" убил боссов 6 и 7
Джию убивает босса № 8 с одним золотом, всего два золота.
отвечать
Первое, о чем мы думаем в этом вопросе, может быть жадность, Например, мы можем думать о жадной стратегии, то есть каждый раз, когда базовый друг убивает монстра, сначала убейте 1, а затем посмотрите, является ли второй 0 или 1, если 0, то Убиваем их вместе, иначе не убиваем и оставляем это "мне".
Мы можем использовать метод оценки эквивалентности, введенный ранее, чтобы судить о том, выполнима ли эта жадная стратегия.Для этой проблемы суть жадности состоит в том, чтобы минимизировать количество криптонитов. Поэтому, когда второй монстр базового друга равен 0, убийство или не убийство не влияет на текущее количество криптонового золота. ноповлияет на последний, и могут иметь разные результаты.
Например, мы можем найти пример 10011. То, убивает ли базовый друг второго монстра, напрямую влияет на последующие результаты. Если базовый друг убит, то как бы ни выбрал "я", базовый друг должен заплатить хотя бы еще раз. Если базовый друг не убивает, то "я" убивает второго монстра, базовый друг убивает третьего монстра, а последние два босса сдаются "мне", то базовому другу требуется криптоновое золото только один раз. Таким образом, жадный алгоритм невозможен.
динамическое программирование
Если вы знакомы с динамическим программированием, то можете обнаружить, что это почти классика.динамическое программированиепроблема. У каждого монстра есть два состояния: быть убитым друзьями или убитым «мной». Мы используем 0 и 1 для представления соответственно, 0 означает быть убитым другом, а 1 означает быть убитым «я». Всего имеется n монстров, поэтому мы можем использовать массив n*2 для записи состояния всех монстров.
Для i-го монстра, если он был убит "I", то его можно получить путем передачи состояния базового друга, убившего i-1 или i-2 монстров. Например, если передано от базового друга, который убил i-1, то это означает, что «я» убил i, в противном случае, это означает, что «я» не только убил i, но и убил i-1. Точно так же ситуация, когда i убит другом, такая же, поэтому это уравнение перехода состояния очень очевидно.
import sys
t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int, input().split(' ')))
dp = [[sys.maxsize, sys.maxsize] for _ in range(n+2)]
dp[0][1] = 0
for i in range(1, n+1):
if i > 1:
# 如果i > 1,那么说明可以杀两个
# 0表示基友杀怪的情况,基友可以杀1个从i-1转移得到,也可以杀2个从i-2转移得到
# 需要加上氪金的次数
dp[i][0] = min(dp[i-1][1] + arr[i-1], dp[i-2][1] + arr[i-2] + arr[i-1])
# 我杀怪不用氪金,直接赋值即可
dp[i][1] = min(dp[i-1][0], dp[i-2][0])
else:
# i=1,那么只能杀一个
dp[i][0] = dp[i-1][1] + arr[i-1]
dp[i][1] = dp[i-1][0]
print(min(dp[n][0], dp[n][1]))
Этот вопрос очень простой, и можно сказать, что он является основной проблемой динамического программирования. Если вы не очень хорошо знакомы с концепцией динамического программирования, настоятельно рекомендуется сделать это самостоятельно, чтобы углубить свое впечатление.
Желаю всем удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)
Оригинальная ссылка, обратите внимание
В этой статье используетсяmdniceнабор текста
- END -