DP 優化方法合集

来源:https://www.cnblogs.com/Jerry-Jiang/archive/2022/08/09/16565671.html
-Advertisement-
Play Games

0. 前言 寫完這篇文章後發現自己對於 DP 的優化一竅不通,所以補了補 DP 的一些優化,寫篇 blog 總結一下。 1. 單調隊列/單調棧優化 1.2 演算法介紹 這應該算是最基礎的 DP 優化方法了。 顧名思義,單調隊列/單調棧優化 DP 就是保持容器內元素的單調性,以達成減少冗餘狀態的目的。 ...


0. 前言

寫完這篇文章後發現自己對於 DP 的優化一竅不通,所以補了補 DP 的一些優化,寫篇 blog 總結一下。

1. 單調隊列/單調棧優化

1.2 演算法介紹

這應該算是最基礎的 DP 優化方法了。

顧名思義,單調隊列/單調棧優化 DP 就是保持容器內元素的單調性,以達成減少冗餘狀態的目的。

舉單調隊列的例子來說,當一個元素的兩種屬性(例如下標和權值)都優於另一元素時,就可以用此元素更換掉另一元素。這也正是 OI 界流傳說法“當一個人比你小且比你強時,你就被彈出單調隊列了”的原理。

我們以下麵的例題作為例子來更具體地闡述這個演算法。

1.3 適用範圍&區別

一般來說,形如 \(f(i)=\max(f(j)+F(i)+F(j))\) 的式子都可以考慮適用單調隊列/單調棧進行優化。(其中 \(F(i)\)\(F(j)\) 表示和 \(i,j\) 有關的函數)

應該大部分人剛學這兩種東西的時候都有一種疑惑:啥時候用單調隊列,啥時候用單調棧呢?(至少我有

其實,它們兩的本質區別還是其結構上的區別。單調棧通常用新加進來的東西替換掉一些棧頂元素,而單調隊列是可能兩端同時修改的。

在一下例題中我也會著重分析兩者的使用。

1.4 例題

I. P1886 滑動視窗

題目鏈接

這個不是優化 DP,就是最經典的裸的不能再裸的單調隊列。

大力單調隊列即可,時間複雜度 \(O(n)\)

II. CF372C Watching Fireworks is Fun

題目鏈接
OI Wili 推薦的題

題目大意:一個數軸上有 \(n\) 個點,每個點在位置 \(a_i\),有 \(m\) 個煙花要放,開始時間 \(t_i\)。你一開始的位置隨便,每一單位時間可以最多走 \(d\) 這麼多的距離,在 \(x\) 看到第 \(i\) 個煙花的快樂值為 \(b_i-|a_i-x|\),求最大的總代價。

數據範圍:\(n\leq 150000,m\leq 300\)

看到這個數據範圍就知道大概是 \(O(nm)\) 的演算法(最多要卡卡常)。

我們容易設計出 DP 狀態 \(f(i,j)\) 表示放第 \(i\) 個煙花,位置在 \(j\) 時的最大快樂值。

轉移:\(f(i,j)=\max_{j-(t_i-t_{i-1})\cdot d_i\leq k\leq j+(t_i-t_{i-1})\cdot d_i}(f(i-1,k)+b_i-|a_i-j|)\)

接下來就需要對 DP 進行優化了,首先因為當 \(i\)\(j\) 確定時 \(b_i-|a_i-j|\) 可以看做常數,剩下的就可以用單調隊列去維護了。

註:本題使用單調隊列的原因為 \(k\) 兩邊都有限制,需要頭尾都更新。

時間複雜度 \(O(nm)\)

代碼

III. P3572 [POI2014]PTA-Little Bird

題目鏈接

IV. P1973 [NOI2011] NOI 嘉年華

題目鏈接

V. P2254 [NOI2005] 瑰麗華爾茲

題目鏈接

2. 斜率優化

斜率優化自己學過好幾遍,也聽 dalao 講過,但是總是感覺半懂不懂的。這次索性把它給搞徹底了罷……

2. 1 演算法介紹

以 OI Wiki 上的例題為例。

題目大意:有 \(n\) 個玩具,每個玩具有一個價值 \(c_i\)。你需要將這 \(n\) 個玩具分成若幹段,設一段 \([l,r]\) 的代價為 \((r-l+\sum_{i=l}^rc_i-L)^2\),其中 \(L\) 為常數,求最小的總代價。

數據範圍:\(n\leq 5\times 10^4\)

使用 DP 優化的一般思路:先設計出一個超時的 DP 再優化。

\(f_i\) 表示前 \(i\) 個玩具的代價,那麼得出轉移方程為:

\[f_i=\min_{j=0}^{i-1}\{f_j+(i-j-1+\sum_{k=j+1}^ic_k+L)^2\} \]

用首碼和表示後即為:

\[f_i=\min_{j=0}^{i-1}\{f_j+(i-j-1+S_i-S_j+c_k+L)^2\} \]

其中 \(S_i=\sum_{k=1}^ic_k\)

這就是朴素的 \(O(n^2)\) 的 DP。

下麵就要優化了,不過有個問題:DP 跟斜率有什麼關係呢?

考慮將 DP 轉移方程轉化為解析幾何中直線的斜截式方程 \(y=kx+b\) 的形式。

我們先將只和 \(i,j\) 有關的歸為一類,常數歸為一類:\(a_i=s_i+i,b_i=s_i+i+L+1\),然後原式可以寫成:

\[f_i=\min_{j=0}^{i-1}\{f_j+(a_i-a_j)^2\} \]

然後可以令 \(y=f_j+b_j^2,k=2a_i,x=b_j\)。(P.S. 這個應該只要滿足 \(y=kx+b\) 都可以?)

此時需要最小化直線的截距,先將這些 \((x,y)\) 表示在平面直角坐標系中:

image

可以看到藍線連成了一個下凸殼,第一個紅線碰到的點使截距最小。

下麵的問題就是怎樣維護這個凸包,發現存在斜率遞增,所以可以用單調隊列來維護。

代碼

2.2 例題

I. P4072 [SDOI2016]征途

題目鏈接

998244352. 參考資料

第 1 章:

第 2 章:

本文來自博客園,作者:Jerry_Jiang,轉載請註明原文鏈接:https://www.cnblogs.com/Jerry-Jiang/p/16565671.html


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 技術 Leader 是一個對綜合素質要求非常高的崗位,不僅要有解具體技術問題的架構能力,還要具備團隊管理的能力,更需要引領方向帶領團隊/平臺穿越迷茫進階到下一個境界的能力。所以通常來說技術 Leader 的技能是虛實結合的居多,繁雜的工作偏多。為此我把自己在工作中經常用到的思考技巧也做了一個整理。 ...
  • 社交是一種永恆的需求,既有生存層面的必要,也有情感上的渴求。而隨著互聯網開始統治這個時代,社交被搬到了網上,並且越來越成為主流,社交也在發展成互聯網產品的一個重要賽道。本文將介紹Soul是如何破解Z世代社交密碼的。 文章目錄 01 年輕人的社交密碼 02 為什麼對年輕人來說,Soul是那個對的產品? ...
  • 統一術語(戰略設計) 我們將通過DDD完成業務與技術的完整落地 統一 領域模型術語 DDD模式名稱 技術 技術設計術語 技術術語 技術設計模式 業務 領域模型術語 DDD模式名稱 業務術語 設計無關的業務術語 清晰的事件流 DDD 領域驅動設計是一個有關軟體開發的方法論,它提出基於領域開發的開發模式 ...
  • 3、ElasticSearch搜索結果處理 3.1、排序 Elasticsearch預設是根據相關度算分(_score)來排序,但是也支持自定義方式對搜索結果排序,可以排序的欄位類型有如下幾種 keyword類型 數值類型 地理坐標類型 日期類型 ... 3.1.1、普通欄位排序 keyword、數 ...
  • @Autowired註解是spring用來支持依賴註入的核心利器之一,但是我們或多或少都會遇到required a single bean, but 2 were found(2可能是其他數字)的問題,接下來我們從源碼的角度去看為什麼會出現這個問題,以及這個問題的解法是什麼? 首先我們寫一個demo ...
  • 2、ElasticSearch高級搜索 Elasticsearch提供了基於JSON的DSL(Domain Specific Language)來定義查詢。常見的查詢類型如下所示 ①、查詢所有 查詢出所有數據,一般測試用;例如 match_all 如下圖所示 ②、全文檢索(full text)查詢 ...
  • Java多線程基礎入門 參考:b站-狂神-多線程詳解 練習與演示代碼見gitee:https://gitee.com/yuhaozhee/java-learning-record ...
  • 1.ObjectPostProcessor 使用 前面介紹了 ObjectPostProcessor的基本概念。相信讀者已經明白,所有的過濾器都由對應的配置類來負責創建,配置類在將過濾器創建成功之後,會調用父類的postProcess方法,該 方法最終會調用到CompositeObjectPostP ...
一周排行
    -Advertisement-
    Play Games
  • 前言 當別人做大數據用Java、Python的時候,我使用.NET做大數據、數據挖掘,這確實是值得一說的事。 寫的並不全面,但都是實際工作中的內容。 .NET在大數據項目中,可以做什麼? 寫腳本(使用控制台程式+頂級語句) 寫工具(使用Winform) 寫介面、寫服務 使用C#寫代碼的優點是什麼? ...
  • 前言 本文寫給想學C#的朋友,目的是以儘快的速度入門 C#好學嗎? 對於這個問題,我以前的回答是:好學!但仔細想想,不是這麼回事,對於新手來說,C#沒有那麼好學。 反而學Java還要容易一些,學Java Web就行了,就是SpringBoot那一套。 但是C#方向比較多,你是學控制台程式、WebAP ...
  • 某一日晚上上線,測試同學在回歸項目黃金流程時,有一個工單項目介面報JSF序列化錯誤,馬上升級對應的client包版本,編譯部署後錯誤消失。 線上問題是解決了,但是作為程式員要瞭解問題發生的原因和本質。但這都是為什麼呢? ...
  • 本文介紹基於Python語言中TensorFlow的Keras介面,實現深度神經網路回歸的方法。 1 寫在前面 前期一篇文章Python TensorFlow深度學習回歸代碼:DNNRegressor詳細介紹了基於TensorFlow tf.estimator介面的深度學習網路;而在TensorFl ...
  • 前段時間因業務需要完成了一個工作流組件的編碼工作。藉著這個機會跟大家分享一下整個創作過程,希望大家喜歡,組件暫且命名為"easyFlowable"。 接下來的文章我將從什麼是工作流、為什麼要自研這個工作流組件、架構設計三個維度跟大家來做個整體介紹。 ...
  • 1 簡介 我們之前使用了dapr的本地托管模式,但在生產中我們一般使用Kubernetes托管,本文介紹如何在GKE(GCP Kubernetes)安裝dapr。 相關文章: dapr本地托管的服務調用體驗與Java SDK的Spring Boot整合 dapr入門與本地托管模式嘗試 2 安裝GKE ...
  • 摘要:在jvm中有很多的參數可以進行設置,這樣可以讓jvm在各種環境中都能夠高效的運行。絕大部分的參數保持預設即可。 本文分享自華為雲社區《為什麼需要對jvm進行優化,jvm運行參數之標準參數》,作者:共飲一杯無。 我們為什麼要對jvm做優化? 在本地開發環境中我們很少會遇到需要對jvm進行優化的需 ...
  • 背景 我們的業務共使用11台(阿裡雲)伺服器,使用SpringcloudAlibaba構建微服務集群,共計60個微服務,全部註冊在同一個Nacos集群 流量轉發路徑: nginx->spring-gateway->業務微服務 使用的版本如下: spring-boot.version:2.2.5.RE ...
  • 基於php+webuploader的大文件分片上傳,帶進度條,支持斷點續傳(刷新、關閉頁面、重新上傳、網路中斷等情況)。文件上傳前先檢測該文件是否已上傳,如果已上傳提示“文件已存在”,如果未上傳則直接上傳。視頻上傳時會根據設定的參數(分片大小、分片數量)進行上傳,上傳過程中會在目標文件夾中生成一個臨 ...
  • 基於php大文件分片上傳至七牛雲,使用的是七牛雲js-sdk V2版本,引入js文件,配置簡單,可以暫停,暫停後支持斷點續傳(刷新、關閉頁面、重新上傳、網路中斷等情況),可以配置分片大小和分片數量,官方文檔https://developer.qiniu.com/kodo/6889/javascrip ...