INOI 2011问题2: IOI训练营20xx (Python)

Question

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

我们已经进入了21世纪，小学生在4班学习动态编程。IOI训练营已经退化为无穷无尽的测试序列，带有负分。在训练营结束时，根据整个测试序列中最佳连续分数段(即没有间隙)的总和对每个学生进行评估。

然而，这些年来，学生们并没有太大的变化，他们要求在评估程序上有所放松。作为一项让步，训练营协调员同意允许学生在计算他们的最佳部分时最多参加一定数量的测试。

例如，假设Lavanya是训练营的一名学生，并且已经进行了十次测试，其中她的分数如下所示。

测试1 2 3 4 5 6 7 8 9 10

标记6 -5 3 -7 6 -1 10 -8 -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

(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)       

Answer 3

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)