解题思路
本题是在一维序列上 选 m 个位置，使相邻被选下标之差的绝对值 ≥k，并 最大化需求和。等价于：若按从小到大选下标 i1<i2<⋯<im，则要求 it+1−it≥k（0-based 同样成立）。
动态规划：设 dp[i][c] 表示在前缀 0∼i 中恰好选 c 个充电站，且 最后一个 选在位置 i 时的最大总和。
- 初始化：dp[i][1]=demands[i]；
- 转移（c≥2）：上一个站必须在 i−k 及之前，dp[i][c]=demands[i]+0≤j≤i−kmaxdp[j][c−1]
P14387.充电桩最优布局规划(200分)
题目内容
某城市计划在一条主要街道两侧建设电动汽车充电桩，以满足日益增长的充电需求。街道被划分为 n 个连续的区域，每个区域都有预估的充电需求量。
为了最大化投资效益，规划部门希望选择 m 个区域建设大型充电站（每个充电站占据一个区域），并且要求任意两个充电站之间的距离至少为 k 个区域。
给定街道各区域的充电需求预测数据，请帮助规划部门确定最优的充电站布局方案，使得所选区域的充电需求总和最大。
注意：距离是指两个区域索引之间的差值，例如区域 i 和区域 j 之间的距离为 abs(i−j)。
输入描述
三个整数 n、m、k，分别表示区域总数、计划建设的充电站数量、充电站间的最小距离要求
整数数组，表示各区域的充电需求量
区域数量 n：1≤n≤2000
充电站数量 m：1≤m≤200
最小距离 k：1≤k≤100
各区域充电需求：0≤ 需求 ≤10000
输出描述
返回一个整数，表示在满足约束条件下能够获得的最大充电需求总和。
注意：测试用例保证输入数据合法，至少存在一种满足条件的选址方案
样例1
输入
5,2,3,[10,20,30,40,50]
输出
70
说明
区域数量：5，计划建设 2 个充电站，最小间距 3
各区域需求：[10,20,30,40,50]
最优选择：选择区域 2(20) 和区域 5(50)，它们之间距离为 3，满足最小距离要求
最大总需求：20+50=70
样例2
输入
5,2,2,[5,10,5,10,5]
输出
20
说明
区域数量：5，计划建设 2 个充电站，最小间距 2
各区域需求 [5,10,5,10,5]
最优选择：选择区域 2(10) 和区域 4(10)，它们之间距离为 2，满足最小距离要求
最大总需求：10+10=20
样例 3
输入
1,1,1,[10]
输出
10
说明
区域数量：1，计划建设 1 个充电站，最小间距 1
各区域需求 [10]
最优选择：选择区域 1(10)，只有 1 个，满足最小距离要求
最大总需求：10
