當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

斜率优化dp 的简单入门

發布時間：2024/3/12 编程问答 32 豆豆

生活随笔收集整理的這篇文章主要介紹了斜率优化dp 的简单入门小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

不想寫什么詳細的講解了...而且也覺得自己很難寫過某大佬（大米餅），于是建議把他的 blog 先看一遍，然后自己加了幾道題目以及解析...順便建議看看算法競賽（藍皮書）的 0x5A 斜率優化（P294）部分

這是——大米餅大佬

看完了大米餅同志對斜率優化的介紹，下面我來稍微講講對斜率優化dp 的理解

前置知識

單調隊列（棧）

平面直角坐標系

直線解析式

等式處理

dp狀態設計

balabala......

理解

其實斜率優化 dp 的原理很簡單：

根據題目（斜率優化 dp 的題目一般都很裸）的?題意?以及?數據范圍?先根據設計一個狀態出來，當做 dp 數組。

根據已經設計好的 dp 狀態設計一個狀態轉移方程，如果設計失敗則跳回第一步，重新設計 dp 狀態。

在第二步完成后，我們一般可以得到這樣的一個式子：$ Fi = Fj +$ $(一個表達式)$?

根據設計的狀態做一些亂七八糟的東西（比如說將式子展開啦，移項啦...這些大米餅講的應該挺清楚的吧）。

在第四步中，我們在將式子展開后，把下標中同時帶有 i、j 的項（注意這里是項，如 S_i*S_j）移到等式的左邊。

然后我們就可以得到一個 $b + k x = y$ 形態的一般式（大米餅是這么叫的），其中等式左邊下標帶有 i 的變量（注意這里是變量，如S_i）作為 k ，下標帶有 j 的變量作為 x ，等式右邊下標帶有 j 的變量作為 y ，至于等式右邊那些下標只帶有 i 的變量我們不去管它，因為 i 在當前對于 Fi 的計算中相當于一個常量，對結果的影響一定。

然后我們發現這時候我們就可以得到點 (x, y) 了，那么我們就基本上已經完成了這道斜率優化 dp 題了。

那么我們是要根據題意讓 Fi （也就是一般式中的 b ）取到最小（大）值，那么我們的任務也就轉化成了過一個點，畫一條斜率為 k 的射線，令其與 y 軸的截距（與 y 軸的交點和原點的距離叫做截距）最小（大）。

做完這些工作之后，你把所有的點畫到平面直角坐標系上，就可以看到這樣的一條折線（假設我們現在求的是 Fi 的最小值）：

沒錯，這就是可能有用的點形成的像凸包一樣的東西（凸殼）。那為什么這些點形成的折線一定是向下凸起的呢？

我們可以想想一下，如果折線內凹，那么引起內凹的那個點可能成為有用點嗎？不可能，因為經過該點的斜率為 k 的直線與 y 軸的截距必然不會比它旁邊兩個點的截距要小

那么我們在來考慮一下，如果我們要求的是 Fi 的最大值呢？那么我們只要讓折線向上凸起就好了（維護上凸性）。

對了對了！還有一點蠻重要的。那就是斜率優化可行性判定的標準（我自己口胡的）：我們在上面的步驟中會處理出一個一般式中的 k 嗎？那個 k 要滿足單調性，

不然是沒辦法用雙端隊列（單調隊列）維護的。

然后這里有一些題目

題目

洛谷P4072?[SDOI2016]征途?

分析

首先你在做這題之前最好已經做過了洛谷P3648?[APIO2014]序列分割?這道題（上面的 T6）。

這道題你只要一直推推推把式子推出來，然后發現 $ans = m * \sum_{i=1}^{m}a[i]^{2} - sum[n]^{2}$ ，

那么你就能知道我們要求的是 $min{\sum_{i=1}^{m}a[i]^{2}}$ （這就是序列分割啊），最后答案處理一下就好了。

代碼

1 //by Judge 2 #include<iostream> 3 #include<cstdio> 4 #define ll long long 5 using namespace std; 6 const int M=3111; 7 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline int read(){ 10 int x=0,f=1; char c=getchar(); 11 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; 12 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; 13 } 14 ll n,m,sum[M],g[M],f[M],q[M],head,tail; 15 inline double Rate(ll i,ll j){ 16 if(sum[i]==sum[j]) return -1e9; 17 return (g[j]-g[i]+sum[j]*sum[j]-sum[i]*sum[i])/(1.0*sum[j]-sum[i]); 18 } 19 signed main(){ 20 n=read(),m=read(); 21 for(int i=1;i<=n;++i) 22 sum[i]=sum[i-1]+read(),g[i]=sum[i]*sum[i]; 23 for(int k=2,i;k<=m;++k){ 24 head=tail=0; 25 for(i=1;i<=n;++i){ 26 while(head<tail && Rate(q[head+1],q[head])<=2*sum[i]) ++head; 27 f[i]=g[q[head]]+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]]); 28 while(head<tail && Rate(q[tail-1],q[tail])>=Rate(q[tail],i)) --tail; q[++tail]=i; 29 } swap(f,g); 30 } printf("%lld\n",g[n]*m-sum[n]*sum[n]); return 0; 31 }

洛谷P4360?[CEOI2004]鋸木廠選址?

分析

首先這道題其實與倉庫建設類似，同時（可以算是）綜合了序列分割...但是數據的處理有點麻煩（甚至還有點坑，比如 d 和 w 搞反了然后樣例里面 d 、w 讀入雷同...）

這題偷懶一點就是?抄 ?綜合一下序列分割這道題，將它作為模板，K 設成 3 ，n 要加一，然后常規做就好了。推式子也不是很麻煩，和倉庫建設一樣的套路

代碼

1 //by Judge 2 #include<iostream> 3 #include<cstdio> 4 #define int long long 5 #define ll long long 6 using namespace std; 7 const int M=5e4+111; 8 #ifdef ONLINE_JUDGE 9 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 10 #endif 11 char buf[1<<21],*p1=buf,*p2=buf; 12 inline int read(){ 13 int x=0,f=1; char c=getchar(); 14 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; 15 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; 16 } 17 ll n,K,x[M],w[M],s[M],g[M],f[M],q[M],head,tail; 18 inline double Rate(ll i,ll j){ 19 if(w[i]==w[j]) return -1e18; 20 return (g[j]-g[i]+s[j]-s[i])/(1.0*w[j]-w[i]); 21 } 22 int las[M]; 23 signed main(){ 24 n=read()+1; 25 for(int i=1;i<=n;++i) 26 (i<n)&&(w[i]=read(),x[i+1]=x[i]+read()), 27 s[i]=s[i-1]+x[i]*w[i],w[i]+=w[i-1],g[i]=1e18; 28 for(int k=1,i;k<=3;++k){ 29 head=tail=0; 30 for(i=1;i<=n;++i){ 31 while(head<tail && Rate(q[head+1],q[head])<=x[i]) ++head; 32 f[i]=g[q[head]]+x[i]*(w[i-1]-w[q[head]])-s[i-1]+s[q[head]]; 33 while(head<tail && Rate(q[tail-1],q[tail])>=Rate(q[tail],i)) --tail; q[++tail]=i; 34 } swap(f,g); 35 } printf("%lld\n",g[n]); return 0; 36 }

其他題...咳咳（來自刷題慢者的尷尬...做一道題都要在黑板上墨跡個半天QwQ）

洛谷P2365?任務安排?

分析

這道題...其實蠻（不）簡單的啦。這題你要消除后效性才能做（其實這是一道經典題目，算法競賽上都有）。

一開始我們讓 $1~n$ 這一整段為一個區間，現在我們考慮當前將$ 1 ~ i $這一區間分為一段，

那么后面所有的任務（以及 $1 ~ i$ 這段區間）必定會多加上 S 時間的代價（即 $S * (C_{n}-C_{1})$，其中 C 為 c 數組的前綴和），而后面區間的分割并不會對前面的分割造成影響。

同理， i 之后的區間我們也可以按照這個思路分下去，以消除后效性。那么我們現在就可以列出狀態轉移方程：$ Fi = Fj + (Cj-Ci)*xi + (Cn-Cj)*S $ 然后展開式子移項后我們就可以斜率優化了。

代碼

1 //by Judge 2 #include<iostream> 3 #include<cstdio> 4 #define mid (l+r>>1) 5 #define ll long long 6 using namespace std; 7 const int M=1e6+111; 8 #ifdef online_judge 9 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 10 #endif 11 char buf[1<<21],*p1=buf,*p2=buf; 12 inline int read(){ 13 int x=0,f=1; char c=getchar(); 14 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; 15 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; 16 } 17 ll n,S,head,tail,q[M],t[M],c[M],f[M]; 18 inline double X(int i){ return c[i]; } 19 inline double Y(int i){ return f[i]-c[i]*S; } 20 inline double Rate(int i,int j){ return (Y(j)-Y(i))/(X(j)-X(i)); } 21 signed main(){ 22 n=read(),S=read(); 23 for(int i=1;i<=n;++i) t[i]=t[i-1]+read(),c[i]=c[i-1]+read(); 24 for(int i=1;i<=n;++i){ 25 while(head<tail && Rate(q[head+1],q[head])<=t[i]) ++head; 26 f[i]=f[q[head]]+(c[n]-c[q[head]])*S+(c[i]-c[q[head]])*t[i]; 27 while(head<tail && Rate(q[tail],q[tail-1])>=Rate(i,q[tail])) --tail; q[++tail]=i; 28 } printf("%lld\n",f[n]); return 0; 29 }

洛谷CF311B?Cats Transport?

分析

沒什么好分析的和上面一樣公式套取就好了（套個鬼哦）。

咳咳。首先你要分析怎么把這道題硬設計出 dp 狀態。那么我們來看看，其實路程對于問題的影響并不顯得有多么重要，于是我們可以考慮消除這個影響。

如何消除？題目中說，飼養員（說好的鏟屎官...）到達貓的位置所需時間就是距離 $X_{i}$，那么其實貓在 $T_{i}$ 的時間開始等待，而飼養員出發時間對于我們要求的答案是沒有影響的（何況題目中說了飼養員出發時間可以為負數），

那么我們可以讓貓開始等待的時間 $T_{i}$ 減去路程的影響 $X_{i}$ （感性理解一下），然后我們再對減完 $X_{i}$ 的 $T_{i}$ 排一下序就好了。

這里如何解釋？emmm...思考一下，一個飼養員出發必然是會接回所有正在等待的貓對吧（貓不可能給下一個人接，那樣不會更優，而上一個人能接回去早接回去了）

咳咳...那么這個飼養員能接到哪些貓呢？當然是 $T-X$（等待開始時間減去路程）小于等于飼養員出發時間的所有貓咯！于是解釋完畢。

排完序后，可以看出我們要接到第 i 只貓的話，它前面的貓我們都可以接到（因為在這只貓之前的貓早就開始等待了）。

于是這道題就變成了分割序列...（切 p 刀，但是注意這里是最多切 p 刀，不一定切完，有的飼養員可以不動的嘛）。

咳咳，但是轉移方程是不一樣的：$ F_{i} = F_{j} + (T_{i}-T_{i-1}) * (i-j) - (T_{i}-T_{j}) $ ?（T 是上文中 $T-X$ 的前綴和數組）

那么這個表達式原來的樣子是：$ F_{i} = MIN{ F_{j} + \sum_{k=j}^{i} ( t_{i}-t_{k} ) ?}$ （這里的 t 是上文中的 $T-X$ 數組）

然后我們就非常愉快的 ctrl+C 、 ctrl+V 將之前打好的序列分割板子弄了下來開始了新一輪的斜率優化。

代碼

1 //by Judge 2 #include<algorithm> 3 #include<iostream> 4 #include<cstdio> 5 #define ll long long 6 using namespace std; 7 const int M=1e5+111; 8 const ll inf=1e16+7; 9 #ifdef ONLINE_JUDGE 10 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 11 #endif 12 char buf[1<<21],*p1=buf,*p2=buf; 13 inline int read(){ 14 int x=0,f=1; char c=getchar(); 15 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; 16 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; 17 } 18 ll n,m,p,ans=inf,d[M],a[M],g[M],f[M],q[M],head,tail; 19 inline double Y(int i){ return g[i]+a[i]; } 20 inline double X(int i){ return i; } 21 inline double Rate(ll i,ll j){ return (Y(j)-Y(i))/(X(j)-X(i)); } 22 signed main(){ 23 n=read(),m=read(),p=read(); 24 for(int i=2;i<=n;++i) d[i]=d[i-1]+read(); 25 for(int i=1,x,y;i<=m;++i) x=read(),y=read(),a[i]=y-d[x],g[i]=inf; 26 sort(a+1,a+m+1); for(int i=2;i<=m;++i) a[i]+=a[i-1]; 27 for(int k=1,i;k<=p;++k){ 28 head=tail=0; 29 for(i=1;i<=m;++i){ 30 while(head<tail && Rate(q[head+1],q[head])<=a[i]-a[i-1]) ++head; 31 f[i]=g[q[head]]+(a[i]-a[i-1])*(i-q[head])-a[i]+a[q[head]]; 32 while(head<tail && Rate(q[tail-1],q[tail])>=Rate(q[tail],i)) --tail; q[++tail]=i; 33 } swap(f,g); ans=min(ans,g[m]); 34 } printf("%lld\n",ans); return 0; 35 }

BinamotoOJ ?P4709: [Jsoi2011]檸檬

分析

這題就是斜率優化裸題啊！這道題非常值得一做，因為它深刻的告訴了我們，斜率優化可以用單調棧維護！

首先這題就是讓我們吧一個序列分成若干份，然后根據公式計算最大值（注意是最大值，維護折線上凸性）

我們可以非常輕松的看出我們要取的一段區間的左右端點必然是相同的顏色，且我們選擇的顏色就是左右端點的顏色。

（我們每一段只能選一種顏色，那么如果左右端點不同，我們完全可以將與選擇的顏色不同的那一端隔離出來分到另一段區間里，那樣更優）

于是我們在讀入時維護一個 las 指針，指向當前顏色上一次出現的位置，同時記錄每個點之前與該點顏色相同的點有多少個（用 S 數組記錄）。

然后我們將所有顏色第一次出現時的位置壓入單調棧，接著就可以開始 dp 了。

那么 dp 轉移式就是： $$ f[i] = f[j-1] + (s[i]-s[j]+1)*a[i] $$ （其中 i 、j 位置的貝殼顏色相同）

斜率式就是： $$ f[i] + 2*a[i]*s[i]*s[j] = f[j-1] + a[i]*s[j]^{2} - 2*a[i]*s[j] + 2*a[i]*s[i]+a[i]*s[i]^{2}+a[i] $$

$$ X(i)=?s[j] , K=2*a[i]*s[i] $$

$$ Y(i)=?f[j-1] + a[i]*s[j]^{2} - 2*a[i]*s[j] $$

代碼

1 //by Judge 2 #include<iostream> 3 #include<cstdio> 4 #include<queue> 5 #define ll long long 6 using namespace std; 7 const int M=1e5+111; 8 //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 inline int read(){ 11 int x=0,f=1; char c=getchar(); 12 for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; 13 for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; 14 } 15 ll n,ans,las[M],a[M],s[M],f[M],top[M]; vector<int> q[M]; 16 inline long double X(int i){ return s[i]; } 17 inline long double Y(int i){ return f[i-1]+a[i]*s[i]*(s[i]-2); } 18 inline long double Rate(ll i,ll j){ return (Y(j)-Y(i))/(X(j)-X(i)); } 19 signed main(){ 20 n=read(); ll p,x,y; 21 for(int i=1;i<=n;++i) a[i]=read(),s[i]=s[las[a[i]]]+1,las[a[i]]=i;; 22 for(int i=1;i<=n;++i) if(las[a[i]]) q[a[i]].push_back(i),las[a[i]]=0; 23 for(int i=1;i<=n;++i){ p=a[i]; 24 while(top[p]>1 && Rate(q[p][top[p]-1],q[p][top[p]])<=Rate(q[p][top[p]],i)) --top[p],q[p].pop_back(); 25 ++top[p],q[p].push_back(i); 26 while(top[p]>1 && Rate(q[p][top[p]-1],q[p][top[p]])<=2*p*s[i]) --top[p],q[p].pop_back(); 27 f[i]=f[q[p][top[p]]-1]+(s[i]-s[q[p][top[p]]]+1)*(s[i]-s[q[p][top[p]]]+1)*p; 28 } printf("%lld\n",f[n]); return 0; 29 }

轉載于:https://www.cnblogs.com/Judge/p/9551035.html

總結

以上是生活随笔為你收集整理的斜率优化dp 的简单入门的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。