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

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)

N = int(input())
arr = list(map(int, input().split()))
 
ways = [(arr[0], [0]), (arr[1], [1])]
 
for i in range(2, N):
    min_index = -1 if arr[i - 1] < arr[i - 2] else -2
    ways.append((arr[i] + ways[min_index][0], ways[min_index][1] + [i]))
 
print(ways[-1][0])
print(*ways[-1][1])

def minimum_pollen(f: list, n):
    c = [0] * len(f)
    c[0], c[1] = f[0], f[1]
    way = [[0]] * len(f)
    way[0], way[1] = [0], [1]
    for i in range(2, len(f)):
        c[i] = min(c[i - 1], c[i - 2]) + f[i]
        way[i] = way[c.index((min(c[i - 1], c[i - 2])), i - 2)] + [i]
    return c[n - 1], way[n - 1]
 
 
n = int(input())
f = list(map(int, input().split()))
tmp1, tmp2 = minimum_pollen(f, n)
print(tmp1)
print(*tmp2)