[IOI训练营20xx(INOI 2011)
我们已经进入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个标记时,您必须计算序列中最佳段的总和。
解决方案提示对于1≤i≤N,1≤j≤K,令Best [i] [j]表示在位置i处终止的最大片段,最多丢弃j个标记。 Best [i] [0]是经典的最大子段或最大子数组问题。当j≥1时;从Best [i] [j-1]归纳计算Best [i] [j]。
输入格式输入的第一行包含两个整数N和K,其中N是要为其提供标记的测试数,K是可以从一个段中删除多少个条目的限制。
这后面是N行输入,每行包含一个整数。在第i + 1行中提供了测试i,i∈{1,2,…,N}的标记。
输出格式输出是单个数字,可以从最多删除K个值的段中获得最大标记。
约束您可以假定1≤N≤104和0≤K≤102。每个测试的标记都在[-104…104]范围内。在40%的情况下,您可以假设N≤250。
def sumsub(ls,k): if k==0: return(sum(ls)) else: ls.sort() if len(ls)>=k: for j in range(0,k): if(ls[0]<0): ls.remove(ls[0]) return(sum(ls)) else: for i in range(len(ls)): if ls[0]<0: ls.remove(ls[0]) return(sum(ls)) n,k= map(int,input().split(" ")) l=[] smax=0 for i in range(n): m=input() l.append(int(m)) for i in range(n): for j in range(n,0,-1): s=sumsub(l[i:j],k) if s>smax : smax=s print(smax)
我得到了正确的答案,但是有时限已经超过了。如果您可以为此提供解决方案,那将有很大的帮助。
[IOI训练营20xx(INOI 2011),我们已经进入21世纪,在第4类中向小学生讲授动态编程。IOI训练营已退化为无穷无尽的序列...