chunlvxiong的博客

T1：防御準備

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

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

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

　　這里就要用到斜率優化DP，下面給出我推導這道題的過程。

　　設i從j轉移比從k轉移要優，那么：

　　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

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

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

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

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

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

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

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

　　用a表示隊尾倒數第二項，用b表示隊尾最后一項，用c表示當前要插入的元素(a<b<c)。

　　可以發現當g(a,b)>g(b,c)時，b不可能成為最優解。

　　1、當g(a,b)>i，表明a優于b，b不是最優解。

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

　　因此可以將b彈出。

　　轉移的時候直接取出隊頭元素進行轉移即可，整個DP復雜度變為O(N)，A掉此題。

　　注意點：上述過程中，請重視正負性的問題，這也許會導致不等式變號，從而改變整個式子。

　　來個簡單點的題目：http://www.lydsy.com/JudgeOnline/problem.php?id=1597（其實這道才是我的入門題啊！）

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

#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的牧場

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

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

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

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

　　你發現b[j+1]到b[i]的系數剛好都是-1下去的，所以你考慮維護一個square數組，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])來表示上面那個式子。

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

　　請仿照上題自行整理成斜率DP的形式，順便總結一下：

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

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

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

　　4、DP時直接取出隊頭元素計算即可。

　　5、千萬注意正負性問題，這是最大的易錯點。（當初之所以搞不懂斜率DP就是因為忽視了正負性的因素）

　　類似的一題：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

　　這個題比較復雜，我們慢慢推。

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

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

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

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

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

　　發現了什么-->兩種割裂方式價值是一樣的-->確定了割裂位置的話，割裂得到價值與割裂順序無關。

　　這個結論的好處就是我們可以直接從開頭一刀刀割向結尾，DP方程變為：(用dp[i][c]表示序列前i項已經割好，且割了c次的最大價值)

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

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

　　利用上述的斜率優化嘗試一下：

　　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]

　　后面隊頭隊尾的維護請自行推導，復雜度可以少一個N，O(NK)應該能過去。

　　本題空間限制128MB，如果開一個100000*200的long long數組=MLE，因此需要滾動數組。

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

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

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

　　好像用乘積式可以解決問題，但是我用乘積式一直WA，所以換了一種更好的解決0問題的方法（對于本題而言），由于本題0的存在毫無意義，在輸入時把ai=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;
}