INOI 2011 Вопрос 2: Учебный лагерь IOI 20xx (Python)

Question

Может кто-нибудь помочь мне с этим вопросом? Мне нужно это решение в python

Мы добрались до 21-го века, и школьники обучаются динамическому c программированию в классе 4. Учебный лагерь IOI выродился в бесконечную последовательность тестов с отрицательными маркировка. В конце лагеря каждый учащийся оценивается на основе суммы наилучшего непрерывного сегмента (то есть без пропусков) оценок в общей последовательности тестов.

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

Например, предположим, что Лаваня учится в тренировочном лагере и что десять тестов, в которых ее оценки следующие.

тест 1 2 3 4 5 6 7 8 9 10

оценки 6 -5 3 -7 6 -1 10 -8 -8 8

В этом случае, если не разрешено отбрасывать какие-либо тесты, лучшим сегментом являются тесты 5–7, которые дают в общей сложности 15 баллов. Если Лаванье разрешено пропустить до 2 тестов в сегменте, лучшим сегментом являются тесты 1–7, что дает в общей сложности 24 оценки после отбрасывания тестов 2 и 4. Если ей разрешено пропустить до 6 тестов в сегменте, лучший результат получается путем взятия всего списка и отбрасывания 5 отрицательных записей, чтобы получить в общей сложности 33.

Вам будет дана последовательность из N тестовых отметок и числа K. Вы должны вычислить сумму лучший сегмент в последовательности, когда до сегмента может быть сброшено до K меток.

Answer 1

Надеюсь, это поможет:

# Read N and K
(N, K) = input().strip().split()
(N, K) = (int(N), int(K))
# Read Marks
marks = []
for i in range(N):
  x = int(input())
  marks.append(x)
#Let Best[i][j] denote the maximum segment ending at position i with at most j marks dropped.
Best = [[0 for i in range(K + 1)] for j in range(len(marks))] 
Best[0][0] = marks[0]
#Filling up Best[i][j] for j = 0, i.e 1 mark dropped.
for i in range(1, len(marks)):
  if marks[i] < (Best[i - 1][0] + marks[i]):
    Best[i][0] = Best[i - 1][0] + marks[i]
  else: 
    Best[i][0] = marks[i]
#Inductively filling the rest of the list(Best)
for j in range(1, K + 1):
  for i in range(len(marks)):
    Best[i][j] = max(Best[i - 1][j - 1], marks[i] + Best[i - 1][j], Best[i][j - 1])
#Finding the maximum
maxMarks = Best[0][K]
for i in range(len(marks)):
  if Best[i][K] > maxMarks:
    maxMarks = Best[i][K]
print(maxMarks)