文章目錄

• 引入
• • acwing154 滑動(dòng)窗口
• 應(yīng)用
• • 135 最大子序和
  • 1088.旅行問(wèn)題
  • AcWing 1087. 修剪草坪28
  • AcWing 1089. 烽火傳遞
  • AcWing 1090. 綠色通道
  • AcWing 1091. 理想的正方形

引入

acwing154 滑動(dòng)窗口

題目鏈接
題解

應(yīng)用

閆氏最優(yōu)化問(wèn)題分析法

135 最大子序和

題目：
輸入一個(gè)長(zhǎng)度為 n 的整數(shù)序列，從中找出一段長(zhǎng)度不超過(guò) m 的連續(xù)子序列，使得子序列中所有數(shù)的和最大。

題解：

我們把這個(gè)問(wèn)題的集合分成n份，第k份表示以A[k]結(jié)尾的最大連續(xù)子序列是多少
我們以A[k]結(jié)尾為例，我們從A[k]開(kāi)始向前延申長(zhǎng)度j，j的范圍是[1,m],我們引入前綴和，S[k]表示前k個(gè)數(shù)的前綴和，那么圖中長(zhǎng)度為j，以A[k]結(jié)尾的連續(xù)子序列答案就是：S[k]-S[k-j],
現(xiàn)在S[k]是固定的，我們要讓值最大，就要使得S[k-j]最小，就相當(dāng)于在長(zhǎng)度為m的區(qū)間（即從[k-m,k]）內(nèi)找最小值,這不就把問(wèn)題引入到滑動(dòng)窗口
時(shí)間復(fù)雜度：O(n)

1088.旅行問(wèn)題

題解
題目：
一個(gè)環(huán)形公路，由n個(gè)車站，每個(gè)站有若干升汽油（有的站可能油量為零），每升油可以讓汽車行駛一千米。
從某個(gè)車站出發(fā)，一直按順時(shí)針（或逆時(shí)針）方向走遍所有的車站，并回到起點(diǎn)。
在一開(kāi)始的時(shí)候，汽車內(nèi)油量為零，John 每到一個(gè)車站就把該站所有的油都帶上（起點(diǎn)站亦是如此），行駛過(guò)程中不能出現(xiàn)沒(méi)有油的情況。
任務(wù)：判斷以每個(gè)車站為起點(diǎn)能否按條件成功周游一周。

題解：
破環(huán)成鏈，鏈復(fù)制
我們從點(diǎn)i出發(fā)，能否到i+1，取決于i的油量是否大于等于d[i]，即i到i+1的距離
所有我們規(guī)定數(shù)組w[i]=a[i]-d[i]
s[i]表示w[i]的前綴和
從i出發(fā)到j(luò)，這個(gè)過(guò)程的油量始終>=0,等價(jià)于在[i,i+n-1]中，對(duì)任意的j，i<=j<=i+n-1,均有s[j]-s[i-1]>=0,如果min(s[j]-s[i-1])>=0,就說(shuō)明能到達(dá)，其中i是固定的，所有就是找s[j]的最小值。
這就把問(wèn)題引到滑動(dòng)窗口，這既是單調(diào)隊(duì)列優(yōu)化
題目中說(shuō)順時(shí)針或逆時(shí)針有一個(gè)就行，所以我們還要倒著來(lái)遍單調(diào)隊(duì)列

AcWing 1087. 修剪草坪28

題解

AcWing 1089. 烽火傳遞

題解

AcWing 1090. 綠色通道

題解

AcWing 1091. 理想的正方形

題解

總結(jié)

以上是生活随笔為你收集整理的Acwing -- 单调队列优化的DP问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。