解题思路
本题是在一维序列上 选 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]