「BZOJ1283」序列

2015年3月25日4,8740

Description

给出一个长度为 的正整数序列Ci,求一个子序列,使得原序列中任意长度为 的子串中被选出的元素不超过K(K,M<=100) 个,并且选出的元素之和最大。

Input

第1行三个数N,m,k。 接下来N行,每行一个字符串表示Ci。

Output

最大和。

Sample Input

10 5 3
4 4 4 6 6 6 6 6 4 4

Sample Output

30

HINT

20%的数据:n<=10。
100%的数据:N<=1000,k,m<=100。Ci<=20000。

题解

线性规划裸题

复习模板ing

题解请看:http://hzwer.com/4831.html与此题类似

本题式子大概是这样

b1 + b2 +…+ bm + y1 = K ————n+2

bm+1 + y2 = b1 + y1

bm+2 + y3 = b2 + y2

bn-m + yn-m+1 = bn + yn

bn-m+1 + … + bn + yn-m+1 = K ————–n+1

 

avatar
  Subscribe  
提醒