一.说人话:

给定长度为 n 的数组 w , w[i] 表示第 i 个元素的权值.

每个元素只有选和不选两种情况

找到一种元素的选择方案,满足如下条件

条件1:相邻被选择的元素间相差至多相隔 m−1 个 不选的元素

条件2:所有被选择的元素权值和最小

二.分析:

典型的最优解问题,考虑使用dp求解

尝试把答案拆分成一个个子集

状态表示: dp[i] 表示 在前 i 个元素范围中  满足条件1且选择第 i 个元素 的所有当前方案 中的最小权值和

状态划分: 已知 最后一个选择的元素是第 i 个,根据倒数第二个被选择的元素的位置( 倒数第二个元素从第 i-m 到第 i-1 个 ), 可以不重不漏的划分为多个子集.

状态转移方程:      dp[i] = min( dp[i-m], dp[i-m+1] ... dp[i-2], dp[i-1] ) + w[i]    ( i-m > = 1 )

最终满足题意的答案为

三.使用单调队列进行优化:

在这个一维状态计算和转移的过程中,求解 min( dp[i-m], dp[i-m+1] ... dp[i-2], dp[i-1] )正好属于移动固定长度区间最小值问题.

因此可以使用 单调队列 进行优化

需要注意的是,从小到大处理状态dp[i]时

dp[i]对应的新的区间的左端点为 i-m ,右端点 为 i-1

也就是说新滑入元素为 dp[i-1] , 新滑出元素为dp[i-m-1]

四.关于最终解的问题:

一般的dp问题的最终解为 dp[n]

然而,在本题中 dp[n] 表示从1->n 满足条件1且选择第 n 个元素 的所有当前方案 中的最小权值和

但是最优方案的第n个元素并不一定需要选择,最后一个选择的元素可能为 第 n-m+1 到 第n个.

所以最优方案应当是 dp[n-m+1]...dp[n-1],dp[n] 的最小值

当然,还有一种码量更简单的解决办法,假设存在第n+1个元素,但权值为0

dp[n+1]表示在前 i+1 个元素范围中  满足条件1且选择第 i+1 个元素 的所有当前方案 中的最小权值和

满足前i+1个元素满足题意,必然前i个满足题意,又因为第i+1个权值为0,不影响最终解的答案

因此最终答案为dp[n+1]

四.代码