解题思路
先把每个元素的“基础贡献”记为：
wi=c×(ai−b)2
如果一段区间长度为 len，删去其中恰好 k 个数后，剩余元素的总贡献为：
P4589.第3题-简单数组划分
题目内容
给定两个整数b,c和一个长度为n的数组a。
你需要将数组a划分为m个连续子数组，覆盖全部元素且互不重叠每段长度至少为k。
我们定义一段数组的贡献为：从该段中删除任意k个数后，剩余元素贡献之和。设该段的原始长度为len(删除前的长度)，其中每个元素ai的贡献定义为：
c×len2×(ai−b)2
请问：如何划分才能使得所有段的总贡献最大？输出该最大贡献值。
输入描述
第一行输入五个整数n(1≤n≤1000)、m(1≤m≤min(n,100))、 k(1≤k≤min(n,100))、b和c，含义如下:
-
n为数组长度
-
n为划分的段数
-
k为每段需要删除的元素个数;
-
b,c为题面参数。
第二行输入n 个整数
a1,a2,...,an(−100≤ai≤100),表示数组元素。
保证m×k≤n。
数据范围：(1≤n≤1000,1≤m≤min(n,100),1≤k≤(n,100),m×k≤n,−100≤ai,b,c≤100)
输出描述
输出一个整数，表示最大的总贡献值。
样例1
输入
5 2 1 0 1
1 3 2 4 5
输出
800
说明
在这个样例中:
- 最优划分为[1]与[3,2,4,5]；
- 在第一段删除元素1，该段无剩余元素，贡献为0
- 在第二段删除最小元素2，剩余元素[3,4,5]，段长度为4，贡献为
1×42×32+1×42×42+1×42×52=144+256+400=800
总贡献为0十800=800。
样例2
输入
3 3 1 0 1
10 20 30
输出
0
说明
当每段长度为1目需要删除1个元素时，各段无剩余元素，因此总贡献为0
