Дана последовательность числе b_1, b_2, …, b_n. Удалить можно любое число, кроме крайних, и штраф за удаление равен произведению этого числа на сумму его соседей. Нужно удалить все числа, кроме крайних, заплатив минимально возможный штраф.
Например:
Начальная последовательность: 3 2 1 4 5 . Удаляем второе число, штраф 2(3+1)=8, получаем 3 1 4 5. Удаляем четвертое число, штраф 4(1+5)=24, получаем 3 1 5. Удаляем третье число, штраф 1*(3+5)=8. Итого штраф 40.
Формат ввода
n (1 ≤ n ≤ 150) – количество чисел в последовательности.
n целых чисел b_1, b_2 ,…, b_n;
Формат вывода
Нужно вывести одно число – минимальный суммарный штраф.
def min_penalty(b):
n = len(b)
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 0
for diag in range(1, n):
for i in range(n - diag):
j = i + diag
for k in range(i + 1, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + b[i] * b[j] * b[k])
return dp[0][n - 1]
n = int(input())
b = list(map(int, input().split()))
print(min_penalty(b))
5
3 2 1 4 5
40
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет