@GeloBer

Как правильно решить задачу про кузнечика путём динамического программирования?

Всем привет! Написал код для решения следующей задачи:

Кузнечик
Кузнечик прыгает по цветам, расположенным на прямой. На каждом цветке находится пыльца. В начале пути кузнечик находится на земле.

Кузнечик может
  • прыгнуть на следующий цветок
  • перепрыгнуть один цветок

Как кузнечику добраться от земли до последнего цветка, запачкавшись меньшим количеством цветочной пыльцы.

Формат входных данных
Две строки. В первой - количество цветков, N. Во второй массив длины N - количество пыльцы (от 1 до 100) на каждом цветке.

Формат выходных данных
Две строки. В первой - минимальное количество пыльцы, которой запачкается кузнечик. Во второй - путь кузнечика. Путь представляет из себя номера цветков, которые посетит кузнечик. Нумерация цветков с нуля.

Примеры
Ввод
3
1 3 1
Вывод
2
0 2

Ввод
4
2 1 5 1
Вывод
2
1 3

Проблема моего кода в том, что он не проходит некоторые тесты, которые от меня скрыты. Проверял код на тетради в ручную, вроде бы всё работает. Прошу объяснить в чём проблема. Заранее спасибо!
def minimum(F: list):
    pollen_array = []
    if len(F) < 3:
        pollen_array.append(0)
        return F[1], pollen_array
    elif len(F) == 3:
        pollen_array.append(F.index(min(F[1], F[2])) - 1)
        return min(F[1], F[2]), pollen_array
    else:
        pollen = 0
        i = 0
        while i < len(F) - 1:
            if i < len(F) - 2:
                pollen += min(F[i + 1], F[i + 2])
                i = F.index((min(F[i + 1], F[i + 2])), i + 1) if F[i + 1] != F[i+2] else i + 2
                pollen_array.append(i - 1)
            elif i == len(F) - 2:
                pollen += F[i + 1]
                pollen_array.append(i)
                break
    return pollen, pollen_array


n = int(input())
F = list(map(int, input().split()))
F.insert(0, 0)

a, b = minimum(F)
print(a)
print(*b)
  • Вопрос задан
  • 199 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вы поняли, что это динамическое программирование. Опишите, что у вас за функция ДП, дайте формулу пересчета, базу и где ответ.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы