chunlvxiong的博客

---

T1：防御準(zhǔn)備

　　 ?三個(gè)月后第一次寫博客，我們從這個(gè)題開始：http://www.lydsy.com/JudgeOnline/problem.php?id=3156。

　　這道題DP方程比較好寫：用dp[i]表示1到i全部被控制的最小代價(jià)，那么dp[i]=min{dp[j]+(i-j)*(i-j-1)/2+a[i]}/*表明j+1到i被i守衛(wèi)*/

　　然后O(N^2)大T特T。

　　這里就要用到斜率優(yōu)化DP，下面給出我推導(dǎo)這道題的過程。

　　設(shè)i從j轉(zhuǎn)移比從k轉(zhuǎn)移要優(yōu)，那么：

　　dp[j]+(i-j)*(i-j-1)/2<dp[k]+(i-k)*(i-k-1)/2
　　dp[j]+[i^2-2ij+j^2-i+j]/2<dp[k]+[i^2-2ik+k^2-i+k]/2
　　dp[j]-dp[k]<[-2ik+k^2+k+2ij-j^2-j]/2
　　dp[j]-dp[k]<[k(k+1)-j(j+1)]/2-(ik-ij)
　　i(k-j)<{k(k+1)/2+dp[k]}-{j(j+1)/2+dp[j]}
　　j<k:{k(k+1)/2+dp[k]}-{j(j+1)/2+dp[j]}/(k-j)>i-->{j(j+1)/2+dp[j]}-{k(k+1)/2+dp[k]}/(j-k)>i
　　j>k:{k(k+1)/2+dp[k]}-{j(j+1)/2+dp[j]}/(k-j)<i-->{j(j+1)/2+dp[j]}-{k(k+1)/2+dp[k]}/(j-k)<i

　　由此可以得到一個(gè)很像斜率的東西：令yi=i(i+1)/2+dp[i],xi=i，那么你發(fā)現(xiàn)這個(gè)式子變成了：

　　j<k:(yj-yk)/(xj-xk)>i

　　j>k:(yj-yk)/(xj-xk)<i

　　這個(gè)東西維護(hù)起來要好很多，因此yj,yk,xj,xk都是不受i的影響的，如果你能把式子化成類似這樣的形式，那么你幾乎已經(jīng)成功了。

　　一般斜率DP使用單調(diào)隊(duì)列進(jìn)行維護(hù)。（下面描述中，我們用g(a,b)表示(ya-yb)/(xa-xb)）

　　隊(duì)頭維護(hù)：本題中優(yōu)于i是遞增的，用a表示隊(duì)列第一項(xiàng)，用b表示隊(duì)列第二項(xiàng)(a<b)，那么g(b,a)<i時(shí)，則以后g(b,a)一定一直小于i，也就是說以后b一定一直優(yōu)于a，那么可以將a彈出。

　　隊(duì)尾維護(hù)：（這個(gè)你也可以畫圖維護(hù)一個(gè)類似凸包的東西，但我更喜歡直接推）

　　用a表示隊(duì)尾倒數(shù)第二項(xiàng)，用b表示隊(duì)尾最后一項(xiàng)，用c表示當(dāng)前要插入的元素(a<b<c)。

　　可以發(fā)現(xiàn)當(dāng)g(a,b)>g(b,c)時(shí)，b不可能成為最優(yōu)解。

　　1、當(dāng)g(a,b)>i，表明a優(yōu)于b，b不是最優(yōu)解。

　　2、當(dāng)g(a,b)<i，則g(b,c)<g(a,b)<i，表明b劣于c，b不是最優(yōu)解。

　　因此可以將b彈出。

　　轉(zhuǎn)移的時(shí)候直接取出隊(duì)頭元素進(jìn)行轉(zhuǎn)移即可，整個(gè)DP復(fù)雜度變?yōu)镺(N)，A掉此題。

　　注意點(diǎn)：上述過程中，請(qǐng)重視正負(fù)性的問題，這也許會(huì)導(dǎo)致不等式變號(hào)，從而改變整個(gè)式子。

　　來個(gè)簡(jiǎn)單點(diǎn)的題目：http://www.lydsy.com/JudgeOnline/problem.php?id=1597（其實(shí)這道才是我的入門題啊！）

貼代碼：（注：可以用乘積式代替g函數(shù)）

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1000005; int n,front,rear; ll a[maxn],dp[maxn],q[maxn]; ll y(ll a){return a*(a+1)/2+dp[a]; } ll x(ll a){return a; } double g(ll a,ll b){return (1.0*(y(a)-y(b)))/(1.0*(x(a)-x(b))); } int main(){scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%lld",&a[i]);dp[0]=0;front=rear=0,q[rear++]=0;for (ll i=1;i<=n;i++){while (front<rear-1 && g(q[front+1],q[front])<1.0*i) front++;ll t=q[front]; dp[i]=dp[t]+(i-t)*(i-t-1)/2+a[i];while (front<rear-1 && g(q[rear-2],q[rear-1])>g(q[rear-1],i)) rear--;q[rear++]=i;}printf("%lld\n",dp[n]);return 0; }

T2：小P的牧場(chǎng)

　　題目鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=3437

　　這題比上一題不同之處在于，它到控制它的控制站之間的牧場(chǎng)數(shù)目（不包括自身，但包括控制站所在牧場(chǎng)）乘上該牧場(chǎng)的放養(yǎng)量這句話有點(diǎn)礙眼。

　　單單使用一個(gè)sum前綴和似乎不能表示出DP方程。

　　如果i控制j+1到i之間的牧場(chǎng)，那么新的cost就是(i-j-1)*b[j+1]+(i-j-2)*b[j+2]+……+1*b[i-1]+0*b[i]+a[i](a[i]后面忽略不計(jì))

　　你發(fā)現(xiàn)b[j+1]到b[i]的系數(shù)剛好都是-1下去的，所以你考慮維護(hù)一個(gè)square數(shù)組，square[i]=Σb[x]*x|1<=x<=i。

　　然后square[i]-square[j]=b[i]*i+b[i-1]*(i-1)+……+b[j+1]*(j+1)。可以用(sum[i]-sum[j])*i-(square[i]-square[j])來表示上面那個(gè)式子。

　　那么DP方程寫出來了，用dp[i]表示1到i的站被控制的代價(jià)，那么dp[i]=min{dp[j]+(sum[i]-sum[j])*i-(square[i]-square[j])+a[i]}

　　請(qǐng)仿照上題自行整理成斜率DP的形式，順便總結(jié)一下：

　　1、首先要化成(yj-yk)/(xj-xk)<a或者>a的形式，其中yi,xi是只跟i有關(guān)的式子，為了化成這樣的式子，有時(shí)還需要引進(jìn)前綴和等數(shù)組。

　　2、隊(duì)頭處理：考慮a遞增或是遞減的性質(zhì)，然后通過g(x,y)與a的關(guān)系來判斷是否彈出x。

　　3、隊(duì)尾處理：類似于幾何上凸包的形狀，盡管我個(gè)人直接推導(dǎo)更不容易錯(cuò)，即g(x,y)<g(y,z)或g(x,y)>g(y,z)的形式。

　　4、DP時(shí)直接取出隊(duì)頭元素計(jì)算即可。

　　5、千萬注意正負(fù)性問題，這是最大的易錯(cuò)點(diǎn)。（當(dāng)初之所以搞不懂斜率DP就是因?yàn)楹鲆暳苏?fù)性的因素）

　　類似的一題：http://www.lydsy.com/JudgeOnline/problem.php?id=1096

　　再來一題：http://www.lydsy.com/JudgeOnline/problem.php?id=1010

貼本題代碼：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1000005; int n,front,rear,q[maxn]; ll a[maxn],b[maxn],sum[maxn],square[maxn],dp[maxn]; ll x(ll a){return sum[a]; } ll y(ll a){return dp[a]+square[a]; } double g(ll a,ll b){return (1.0*(y(a)-y(b)))/(1.0*(x(a)-x(b))); } int main(){scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%lld",&a[i]);square[0]=sum[0]=0;for (ll i=1;i<=n;i++){scanf("%lld",&b[i]);sum[i]=sum[i-1]+b[i],square[i]=square[i-1]+b[i]*i;}dp[0]=0;front=rear=0,q[rear++]=0;for (ll i=1;i<=n;i++){while (front<rear-1 && g(q[front+1],q[front])<1.0*i) front++;int j=q[front]; dp[i]=dp[j]-(square[i]-square[j])+i*(sum[i]-sum[j])+a[i];while (front<rear-1 && g(q[rear-2],q[rear-1])>g(q[rear-1],i)) rear--;q[rear++]=i;}printf("%lld\n",dp[n]);return 0; }

T3：[Apio2014]序列分割

　　題目鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=3675

　　這個(gè)題比較復(fù)雜，我們慢慢推。

　　最暴力的DP：需要三維，分別存儲(chǔ)本次割點(diǎn)，上次割點(diǎn)，分割次數(shù)，然后再窮舉上上次割點(diǎn)，進(jìn)行轉(zhuǎn)移，復(fù)雜度O(N^3K)=T到無邊無際。

　　然后第一步非常的巧，我們畫個(gè)圖來說明吧：

　　

　　割裂順序有兩種，得到的價(jià)值分別如下：

　　1、先割裂sum1和sum2，再割裂sum2和sum3，價(jià)值為sum1*(sum2+sum3)+sum2*sum3

　　2、先割裂sum2和sum3，再割裂sum1和sum2，價(jià)值為sum3*(sum1+sum2)+sum1*sum2

　　發(fā)現(xiàn)了什么-->兩種割裂方式價(jià)值是一樣的-->確定了割裂位置的話，割裂得到價(jià)值與割裂順序無關(guān)。

　　這個(gè)結(jié)論的好處就是我們可以直接從開頭一刀刀割向結(jié)尾，DP方程變?yōu)?#xff1a;(用dp[i][c]表示序列前i項(xiàng)已經(jīng)割好，且割了c次的最大價(jià)值)

　　利用前綴和優(yōu)化：dp[i][c]=max{dp[j][c-1]+(sum[i]-sum[j])*sum[j]}

　　復(fù)雜度是O(N^2K)的，仍然T的厲害，我們必須再去掉一個(gè)N，O(NK)才能A掉此題。

　　利用上述的斜率優(yōu)化嘗試一下：

　　dp[j][c-1]+(sum[i]-sum[j])*sum[j]>dp[k][c-1]+(sum[i]-sum[k])*sum[k]

　　(dp[j][c-1]-sum[j]^2)-(dp[k][c-1]-sum[k]^2)>sum[i]*(sum[k]-sum[j])

　　令yi=dp[i][c-1]-sum[i]^2,xi=sum[i]

　　j<k:(yj-yk)/(xk-xj)>sum[i]-->(yj-yk)/(xj-xk)<-sum[i]

　　j>k:(yj-yk)/(xk-xj)<sum[i]-->(yj-yk)/(xj-xk)>-sum[i]

　　后面隊(duì)頭隊(duì)尾的維護(hù)請(qǐng)自行推導(dǎo)，復(fù)雜度可以少一個(gè)N，O(NK)應(yīng)該能過去。

　　本題空間限制128MB，如果開一個(gè)100000*200的long long數(shù)組=MLE，因此需要滾動(dòng)數(shù)組。

　　但是這題我調(diào)了很久，下面來好好說一說關(guān)于0的問題（本題(xj-xk)可能為0）

　　到(dp[j][c-1]-sum[j]^2)-(dp[k][c-1]-sum[k]^2)>sum[i]*(sum[k]-sum[j])這一步為止，我們只進(jìn)行加減法，所以這一步的式子是可靠的。

　　那么xj-xk=0，所以要判斷yj-yk是否大于0即可，如果yj-yk>0，那么無論sum[i]等于幾，j都優(yōu)于k。

　　好像用乘積式可以解決問題，但是我用乘積式一直WA，所以換了一種更好的解決0問題的方法（對(duì)于本題而言），由于本題0的存在毫無意義，在輸入時(shí)把a(bǔ)i=0的全部刪去，以保證xj-xk不等于0。

貼代碼：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100005; int n,k,front,rear,q[maxn]; ll a[maxn],sum[maxn],dp[maxn],Dp[maxn]; ll x(ll a){return sum[a]; } ll y(ll a){return dp[a]-sum[a]*sum[a]; } double g(ll a,ll b){return (1.0*(y(a)-y(b)))/(1.0*(x(a)-x(b))); } int main(){scanf("%d%d",&n,&k),sum[0]=0;for (int i=1;i<=n;i++){scanf("%lld",&a[i]);if (!a[i]) n--,i--; else sum[i]=sum[i-1]+a[i];}memset(dp,0,sizeof(dp));for (int c=1;c<=k;c++){front=rear=0,q[rear++]=0;for (int i=1;i<=n;i++){while (front<rear-1 && g(q[front+1],q[front])>-sum[i]) front++;int j=q[front]; Dp[i]=dp[j]+(sum[i]-sum[j])*sum[j];while (front<rear-1 && g(q[rear-2],q[rear-1])<g(q[rear-1],i)) rear--;q[rear++]=i;}for (int i=1;i<=n;i++) dp[i]=Dp[i];}printf("%lld\n",Dp[n]);return 0; }

下面給一道相對(duì)簡(jiǎn)單的題目：http://www.lydsy.com/JudgeOnline/problem.php?id=1911

轉(zhuǎn)載于:https://www.cnblogs.com/chunlvxiong/p/8078426.html

總結(jié)

以上是生活随笔為你收集整理的斜率DP总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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