【動態規劃】5 從一次函數出發推導斜率優化dp

背景

基于例題《任務安排》逐步推導進行斜率優化。

引入

例題：P2365 任務安排

考慮動態規劃。使用 $dp_{i,j}$ 表示前 $i$ 個任務分了 $j$ 段的最小費用。

顯然，有 $dp_{i,j} = \min_{k=1}^{i-1} (dp_{i,j},dp_{k,j-1} + (tot_i-tot_k))*(sum[i]+s*j))$ ? 。

$sum_i$ 表示 $c_i$ 的前綴和。
$tot_i$ 表示 $t_i$ 的前綴和。

前綴和優化后，時間復雜度 $O(n^3)$ ，得到 60pts.

代碼

#include <bits/stdc++.h>
using namespace std;
int n,s,ans,t[5005],c[5005],dp[5005][5005],sum[5005],tot[5005];
int main()
{cin >> n >> s;for (int i=1;i<=n;i++){cin >> t[i] >> c[i];sum[i] = sum[i-1] + t[i];tot[i] = tot[i-1] + c[i];}memset(dp,0x3f,sizeof(dp));ans = 0x3f3f3f3f;dp[0][0] = 0;for (int i=1;i<=n;i++){for (int j=1;j<=i;j++){for (int k=0;k<i;k++){dp[i][j] = min(dp[i][j],dp[k][j-1] + (tot[i]-tot[k])*(sum[i]+s*j));}	}	}for (int i=1;i<=n;i++){ans = min(ans,dp[n][i]);}cout<<ans;return 0;
}

如何進一步優化呢？

我們發現，可以把有關 $s$ 的計算在前面完成。也就是 費用提前計算 ，就不需要枚舉分的段數了。

得到狀態轉移方程 $dp_i = \min(dp_i,dp_j + sum_i*tot_i-sum_i*tot_j + tot_n*s-tot_j*s)$

代碼

#include <bits/stdc++.h>
using namespace std;
long long n,s,ans,t[5005],c[5005],dp[5005],sum[5005],tot[5005];
int main()
{cin >> n >> s;for (int i=1;i<=n;i++){cin >> t[i] >> c[i];sum[i] = sum[i-1] + t[i];tot[i] = tot[i-1] + c[i];dp[i] = 1e18;}ans = 1e18;dp[0] = 0;for (int i=1;i<=n;i++){for (int j=0;j<i;j++){dp[i] = min(dp[i],dp[j] + sum[i]*(tot[i]-tot[j]) + (tot[n]-tot[j])*s);}	}cout<<dp[n];return 0;
}

正文

狀態轉移方程 $dp_i = \min(dp_i,dp_j + sum_i*tot_i-sum_i*tot_j + tot_n*s-tot_j*s)$

把與 $i, j$ 有關的各單獨放在一起，得到 $dp_i = \min(dp_i,dp_j + sum_i*tot_i + tot_n*s - tot_j*(sum_i+s))$

去掉最小值，得到 $dp_i = dp_j + sum_i*tot_i + tot_n*s - tot_j*(sum_i+s)$

移項，得到 $dp_j = tot_j*(sum_i+s) + dp_i - sum_i*tot_i - tot_n*s$

在 $tot_j$ 為橫坐標， $dp_j$ 為縱坐標的平面直角坐標系中，

這是一條 $y = (s+sum_i) * x + dp_i - sum_i * tot_i - tot_n * s$ 的直線。

寫成 $y = k x + b$ 的形式， $k = s+sum_i$ ， $b = dp_i-sum_i*tot_i-tot_n*s$ .

由于 $k$ 是定值，所求的 $dp_i$ 存在于 $b$ 中，所以我們只需要找到最小的 $b$ 即可。

如何尋找最小的 $b$ ？

發現有一些點會出現在這條直線上，我們把這樣的點稱為 決策點，即 $tot_j,dp_j)$ 。

對于這些決策點，由于 $k$ 是定值，所以有且只有一條 $k=s+sum_i$ 的直線經過一個決策點，這些決策點一共會產生不超過 $j$ 條直線。

對于已知的一個決策點 $tot_j,dp_j)$ ，我們把它們帶入到一次函數表達式里去，就能解出一個 $b$ ，枚舉 $j$ 得到最小的 $b$ 即可。

但這種方法過于樸素，時間復雜度不變。考慮優化。

由于我們是從決策點出發，推導 $b$ 的值。則說明決策點坐標（或者說 $j$ ）與 $b$ 之間存在線性關系。考慮決策點坐標之間的關系來優化。

對于三個決策點 $tot_{j_1},dp_{j_1}),(tot_{j_2},dp_{j_2}),(tot_{j_3},dp_{j_3})$ （我們設這三點 $j_1 < j_2 < j_3$ ，由于 $t, c > 0$ ，所以這三點的橫坐標依次遞增，即 $tot_{j_1} < tot_{j_2} < tot_{j_3}$ ）來說，當這三個決策點有且僅有取 $tot_{j_2},dp_{j_2})$ 時， $b$ 有最小值，那么這三點所構成的直線不會兩兩重合，并分為兩種情況：

情況 1 ( $j_2$ 在 $j_1$ 與 $j_3$ 的連線上方)

當這三點構成一個向上凸出的形狀，即上凸。顯然此時 $j_2$ 一定不會使得 $b$ 取最小值，如下圖所示。

情況 2 ( $j_2$ 在 $j_1$ 與 $j_3$ 的連線下方)

當這三點構成一個向下凸出的形狀，即下凸。顯然此時 $j_2$ 可能使得 $b$ 取最小值，如下圖所示。

發現只有下凸的情況 ( $j_2$ 在 $j_1$ 與 $j_3$ 的連線下方) 才可能使 $j_2$ 取到最小的 $b$ 。

則有 $\frac{dp_{j_2}-dp_{j_1}}{tot_{j_2}-tot_{j_1}} < \frac{dp_{j_3}-dp_{j_2}}{tot_{j_3}-tot_{j_2}}$ 。

即直線 $j_1 \to j_2$ 的 $k$ 小于 $j_2 \to j_3$ 直線的 $k$ ，本質上是這兩條直線的斜率關系。

因此，我們需要維護 相鄰兩點間直線的 $k$ （斜率） ，并當它們 單調遞增 時， $j_2$ 所得到的 $b$ 就可能是最小值。

那么什么時候 $j_2$ 所取的 $b$ 就一定是最小值呢？

我們發現，當一段單調遞增的 $k$ 滿足一個點的左邊的 $k ’$ 都小于 $k$ ，右邊的 $k ’$ 都大于 $k$ 時，這個點就是使 $b$ 最小的點。

如果我們只維護 相鄰兩點間連線斜率大于等于 $k$ 的 $k^{'}$ （斜率），那么在這個單調遞增的序列中最小值就能使 $b$ 最小。

這不就是單調隊列的思路嗎？

總結一下：

我們用單調隊列維護相鄰兩點間直線的 $k$ ，使其單調遞增。
在單調隊列里放的是 $k$ 單調遞增的點的編號。
最終答案是單調隊列的隊頭坐標代入 $dp_i = dp_j + sum_i*tot_i + tot_n*s - tot_j*(sum_i+s)$ .
為了維護單調性，我們需要從左側隊頭開始刪除。即判斷隊頭斜率 $\frac{dp_{q_{head+1}}-dp_{q_{head}}}{tot_{q_{head+1}}-tot_{q_{head}}} \leq s+sum_i$ 時，把隊頭出隊即可。為了避免精度問題，且 $t o t$ 有單調遞增性，那么我們不妨判斷 ${dp_{q_{head+1}}-dp_{q_{head}}} \leq (s+sum_i) * ({tot_{q_{head+1}}-tot_{q_{head}}})$ .
添加時，如果 $q_i$ 不能與前面的點滿足單調性，那么直接把前面的點不斷出隊，直到滿足單調性為止。即當 $\frac{dp_{i}-dp_{q_{tail}}}{tot_{i}-tot_{q_{tail}}} \leq \frac{dp_{q_{tail}}-dp_{q_{tail-1}}}{tot_{q_{tail}}-tot_{q_{tail-1}}}$ 時不斷出隊即可。同樣避免精度問題，判斷 $({dp_{i}-dp_{q_{tail}}}) * ({tot_{q_{tail}}-tot_{q_{tail-1}}}) \leq ({dp_{q_{tail}}-dp_{q_{tail-1}}})*({tot_{i}-tot_{q_{tail}}})$ 即可。

時間復雜度 $O (n)$ .

#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
long long n,s,ans,t[N],c[N],dp[N],sum[N],tot[N];
long long q[N],head=1,tail=1;
int main()
{cin >> n >> s;for (int i=1;i<=n;i++){cin >> t[i] >> c[i];sum[i] = sum[i-1] + t[i];tot[i] = tot[i-1] + c[i];dp[i] = 1e18;}ans = 1e18;dp[0] = 0;for (int i=1;i<=n;i++){while (head < tail && dp[q[head+1]]-dp[q[head]] <= (s+sum[i])*(tot[q[head+1]]-tot[q[head]])) head++;dp[i] = dp[q[head]] + sum[i]*tot[i] + tot[n]*s - tot[q[head]]*(sum[i]+s);while (head < tail && (dp[i]-dp[q[tail]])*(tot[q[tail]]-tot[q[tail-1]]) <= (dp[q[tail]]-dp[q[tail-1]])*(tot[i]-tot[q[tail]])) tail--;q[++tail] = i;}cout<<dp[n];return 0;
}

為什么單調隊列初始 head = 1,tail = 1 ，而不能寫作 head = 1,tail = 0 ?
考慮到還有 dp[0] = 0 ，要么把 tail 設為 head ，要么把 tail 設為 head-1 再在隊列里加入 dp[0]。

后記

斜率優化看起來好像的確比想象中抽象很多，希望對大家理解斜率優化有所幫助！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/81905.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/81905.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/81905.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！