【HYSBZOJ】【DP】【斜率优化】1911-[Apio2010]特别行动队

HYSBZOJ 1911 [Apio2010]特别行动队

题目

◇题目传送门◆

题目大意

给定一个数列，将它分为若干个连续的数列，对于每个数列求出其元素和，并代入函数$y=a{x}^2+bx+c(a<0)$后计算出所有序列的值的总和，求出这个最大值。

思路

记$s(i)$为由第一$1$元素至第$i$元素的和。

不难列出状态转移方程：f(i)=max?{f(j?1)+a(s(i)?s(j?1))2+b(s(i)?s(j?1))+c(1≤i≤N,1≤j≤i)}f(i)=\max\{f(j-1)+a(s(i)-s(j-1))^2+b(s(i)-s(j-1))+c(1\le i\le N,1\le j\le i)\}f(i)=max{ f(j?1)+a(s(i)?s(j?1))2+b(s(i)?s(j?1))+c(1≤i≤N,1≤j≤i)}

但是这是一个$O(N^2)$的做法，显然必须超时。

所以我们必须讨论它的单调性从而使用单调队列优化求解。

化简$f(j?1)+a(s(i)?s(j?1){)}^2+b(s(i)?s(j?1))+c$得$f(j?1)+a?s(i{)}^2+b?s(i)+a?s(j?1{)}^2?b?s(j?1)+c+2a?s(i)?s(j?1)$，

记$g(i)=a?s(i{)}^2+b?s(i),h(i)=a?s(i{)}^2?b?s(i)+f(i)$，

则上式可进一步化简为$g(i)+h(j?1)+2a?s(i)?s(j?1)+c$，

取任意的$j_1,j_2$满足$j_2>j_1$：

代入并作差得：$h(j_2?1)?h(j_1?1)+2a?s(i)(s(j_2?1)?s(j_1?1))$，

当上式大于0时，选择$j_1$更好，

则可推出此时$$\frac{h(j_1?1)?h(j_2?1)}{s(j_2?1)?s(j_1?1)}>2a?s(i)$$

由于$s(i)$单调递增，$a<0$，则可使用单调队列维护。

注意：WC2016的课件有误，即未注意到$a<0$这个条件。

参考代码

特别注意：由于$a<0$，各处不等式变换时需要注意不等号的方向！！！

#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int Maxn=1000000;ll N,f[Maxn+5];
ll A[Maxn+5],s[Maxn+5];
ll a,b,c;int q[Maxn+5],head,tail;double T(int j1,int j2) {
    return 1.0*((f[j1]+a*s[j1]*s[j1]-b*s[j1])-(f[j2]+a*s[j2]*s[j2]-b*s[j2]))/(s[j1]-s[j2]);
}int main() {
    #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%lld",&N);scanf("%lld %lld %lld",&a,&b,&c);for(int i=1;i<=N;i++) {
    scanf("%lld",&A[i]);s[i]=s[i-1]+A[i];}head=1,tail=0;f[0]=q[++tail]=0;for(int i=1;i<=N;i++) {
    while(head<tail&&T(q[head],q[head+1])>=2.0*a*s[i])head++;//维护队头：去掉超过的解ll x=s[i]-s[q[head]];f[i]=f[q[head]]+a*x*x+b*x+c;//计算结果，最优解在队头while(head<tail&&T(q[tail-1],q[tail])<=T(q[tail],i))tail--;//维护队尾：对于i与q[tail-1]，i的交点在前面，故应弃掉q[tail-1]q[++tail]=i;//当前点加入队尾}printf("%lld\n",f[N]);return 0;
}