一.說人話:

給定長度為 n 的數(shù)組 w , w[i] 表示第 i 個元素的權(quán)值.

每個元素只有選和不選兩種情況

找到一種元素的選擇方案,滿足如下條件

條件1:相鄰被選擇的元素間相差至多相隔 m?1 個 不選的元素

條件2:所有被選擇的元素權(quán)值和最小

二.分析:

典型的最優(yōu)解問題,考慮使用dp求解

嘗試把答案拆分成一個個子集

狀態(tài)表示: dp[i] 表示 在前 i 個元素范圍中? 滿足條件1且選擇第 i 個元素 的所有當(dāng)前方案 中的最小權(quán)值和

狀態(tài)劃分: 已知 最后一個選擇的元素是第 i 個,根據(jù)倒數(shù)第二個被選擇的元素的位置( 倒數(shù)第二個元素從第 i-m 到第 i-1 個?), 可以不重不漏的劃分為多個子集.

狀態(tài)轉(zhuǎn)移方程:? ? ? dp[i] = min( dp[i-m], dp[i-m+1] ... dp[i-2], dp[i-1] ) + w[i]? ? ( i-m > = 1 )

最終滿足題意的答案為

三.使用單調(diào)隊列進行優(yōu)化:

在這個一維狀態(tài)計算和轉(zhuǎn)移的過程中,求解?min(?dp[i-m], dp[i-m+1] ... dp[i-2],?dp[i-1]?)正好屬于移動固定長度區(qū)間最小值問題.

因此可以使用 單調(diào)隊列 進行優(yōu)化

需要注意的是,從小到大處理狀態(tài)dp[i]時

dp[i]對應(yīng)的新的區(qū)間的左端點為 i-m ,右端點 為 i-1

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

四.關(guān)于最終解的問題:

一般的dp問題的最終解為 dp[n]

然而,在本題中 dp[n] 表示從1->n?滿足條件1且選擇第 n 個元素?的所有當(dāng)前方案 中的最小權(quán)值和

但是最優(yōu)方案的第n個元素并不一定需要選擇,最后一個選擇的元素可能為 第 n-m+1 到 第n個.

所以最優(yōu)方案應(yīng)當(dāng)是 dp[n-m+1]...dp[n-1],dp[n] 的最小值

當(dāng)然,還有一種碼量更簡單的解決辦法,假設(shè)存在第n+1個元素,但權(quán)值為0

dp[n+1]表示在前?i+1?個元素范圍中??滿足條件1且選擇第?i+1?個元素?的所有當(dāng)前方案 中的最小權(quán)值和

滿足前i+1個元素滿足題意,必然前i個滿足題意,又因為第i+1個權(quán)值為0,不影響最終解的答案

因此最終答案為dp[n+1]

四.代碼