INOI 2011问题2：IOI培训营20xx（Python）

Question

有人能帮我回答这个问题吗？ 我需要python的解决方案

我们已经进入21世纪，4班的学生都在学习动态规划。IOI训练营已经沦为一系列没完没了的考试，分数都是负数。在夏令营结束时，根据整个测试顺序中的最佳连续段（即无差距）的总和对每个学生进行评估

然而，这些年来，学生们的变化不大，他们要求在评估过程中放松一些。作为一项让步，夏令营协调员同意允许学生在计算他们的最佳部分时放弃一定数量的测试

例如，假设拉瓦尼亚是训练营的一名学生，她参加了十次考试，成绩如下

测试12345678910

标记6-53-76-110-8-8

在这种情况下，在不允许放弃任何测试的情况下，最好的部分是测试5-7，这将产生总共15分的分数。如果允许Lavanya在一个测试段中最多进行2次测试，那么最好的测试段是测试1-7，在放弃测试2和测试4后，该测试段总共得到24分。如果允许她在一个段中删除多达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)

Answer 2

N,K = list(map(int,input().split()))
final = [0]
output = 0
for i in range(N):
    final.    append(  int    (input()))
score = [[0 for i in range(K+1)] for j in range(N+1)]
for i in range(1, N+1):
    score[i][0] = max(score[i-1][0]+final[i], final[i])
    for j in range(1, min(i+1, K+1)):
        score[i][j] = max(score[i-1][j]+final[i], score[i-1][j-1])
for i in range(1, N+1):
    output = max(output, score[i][K])
print(output)

Answer 3

(Nstr,Kstr) = input().strip().split()
(N,K) = (int(Nstr),int(Kstr))

# Read marks

marks = [ 0 for i in range(N) ]
for i in range(N):
  marks[i] = int(input().strip())

# Initialize best

best = [ [ 0 for j in range(K+1) ] for i in range(N) ]

# Base case, incrementally track best answer
best[0][0] = marks[0]
ans = marks[0]

for j in range(1,K+1):
   best[0][j] = max(marks[0],0)
   ans = max(ans,best[0][j])

# Inductive case
for i in range(1,N):

  # Normal maximum segment
  best[i][0] = max(best[i-1][0],0)+marks[i]
  ans = max(ans,best[i][0])

  # Maximum segment with dropping
  for j in range(1,K+1):
    best[i][j] = max(best[i-1][j]+marks[i],best[i-1][j-1])
    ans = max(ans,best[i][j])

# Final answer
print(ans)