Ограничение по времени: 1
секунда
Ограничение по памяти: 256
мегабайт
Ваш университет вовсю готовится к новому сезону командных олимпиад. Как несложно догадаться, для этого необходимо собрать команду, которая будет представлять учебное заведение.
Всего в университете учатся n
студентов, i
-й из них имеет силу ai
. Для участия в олимпиадах необходимо выбрать ровно k
людей и расположить их в каком‑то порядке. Пусть были выбраны студенты с номерами i1
, i2
, …
, ik
(именно в таком порядке). Тогда слабость команды равна |ai2−ai1|+
|ai3−ai2|+
…+|aik−aik−1|
python
def min_weakness(n, k, a):
dp = [0] * (n+1)
for i in range(1, n+1):
dp[i] = float('inf')
for j in range(1, min(i+1, k+1)):
dp[i] = min(dp[i], dp[i-j] + abs(a[i] - a[i-j]))
return dp[n]
# Пример использования
n = 5
k = 3
a = [0, 1, 2, 4, 5, 10]
result = min_weakness(n, k, a)
print(result)
3
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет