[bzoj 1911] [Apio2010]特别行动队
Description
Input
Output
Sample Input
4
-1 10 -20
2 2 3 4
Sample Output
9
HINT
几天前的考试题,当初十分naive地想到用单调队列做,保存f[j]的最大值,然而忘了看清大括号是套在最外面的.后面就只能写暴力,考完后就开始学斜率优化,看了很多人的题解和博客,总算有点感觉了.
首先dp方程是十分naive地就能推出来的:
[{ f }_{ i }=max{ { f }_{ j }+{ asum _{ k=j+1 }^{ i }{ { A }_{ k } } }^{ 2 }+bsum _{ k=j+1 }^{ i }{ { A }_{ k } } +c}
]
至于大坦克(滑稽)就用前缀和处理一下,就变成了这样:
[{ f }_{ i }=max{ { f }_{ j }+{ a({ sum }_{ i }-{ sum }_{ j }) }^{ 2 }+b{ (sum }_{ i }-{ sum }_{ j })+c} quad (0<j<i)
]
好了,那么斜率优化的过程是怎么实现的呢?
我们设有j<k<i且选k比选j更优.那么就有:
[{ f }_{ j }+{ a({ sum }_{ i }-{ sum }_{ j }) }^{ 2 }+b{ (sum }_{ i }-{ sum }_{ j })+c<{ f }_{ k }+{ a({ sum }_{ i }-{ sum }_{ k }) }^{ 2 }+b{ (sum }_{ i }-{ sum }_{ k })+c
]
展开变一下形就有:
[cfrac { { (f }_{ j }+a{ imes { { sum }_{ j } }^{ 2 }-b imes { sum }_{ j } })-{ (f }_{ k }+a{ imes { { sum }_{ k } }^{ 2 }-b imes { sum }_{ k } }) }{ 2a imes ({ sum }_{ j }-{ sum }_{ k }) } <{ sum }_{ i }
]
这个式子长得就很像斜率的表达式:
[frac { { y }_{ i }-{ y }_{ j } }{ { x }_{ i }-{ x }_{ j } }
]
通过计算,还可以知道slope(i,j)如果小于slope(j,k),那么j点以及j点一下的点都可以舍去.(证明:???)(其实与f[i]相关的那个量就是直线的截距)
我们既然知道这样了,那么我们就可以使用斜率优化了.我们考虑使用单调队列处理.
我们定义一个单调队列,里面从队尾到队头斜率是单调递减的.可以理解成
[slope(tail,tail-1)>slope(tail-1,tail-2)>...>slope(head+1,head)
]
维护单调队列中的斜率单调就可以了.我们应该可以很容易地看到从head到tail最可能成为最优解的就越靠近head.所以我们每次更新f[i]时取出head进行更新.在插入时还要考虑维护单调性,即删除那些斜率比大slope(i,tail)的点(注意:这里的tail指的是操作完成后所确定下来的tail).也就是指在队列中找到一个点恰好接上,正好保持斜率单调性就可以了.
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
static const int maxm=1e6+10;
LL Q[maxm],A[maxm],f[maxm],sum[maxm];
LL a,b,c;
int n,head=1,tail=1;
template<class T>
T sqr(T x){
return x*x;
}
LL get_up(int i){
return f[i]+a*sqr(sum[i])-b*sum[i];
}
LL get_down(int j,int k){
return (a<<1)*(sum[j]-sum[k]);
}
double slp(int k,int j){
return (double)(get_up(j)-get_up(k))/get_down(j,k);
}
LL calc(LL x){
return a*sqr(x)+b*x+c;
}
int main(){
scanf("%d%lld%lld%lld",&n,&a,&b,&c);
for(int i=1;i<=n;i++)
scanf("%lld",&A[i]),sum[i]=sum[i-1]+A[i];
for(int i=1;i<=n;i++){
while(head<tail&&slp(Q[head+1],Q[head])<=sum[i])head++;
f[i]=f[Q[head]]+calc(sum[i]-sum[Q[head]]);
while(head<tail&&slp(i,Q[tail])<=slp(Q[tail],Q[tail-1]))tail--;
Q[++tail]=i;
}
printf("%lld
",f[n]);
return 0;
}