题目

题目描述

你有一支由$n$名预备役士兵组成的部队，士兵从$1$到$n$编号，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如$(i, i + 1,\cdots \cdots, i + k)$的序列
编号为 i 的士兵的初始战斗力为$x_i$ ，一支特别行动队的初始战斗力$x$为队内士兵初始战斗力之和，即$x = \sum\limits_{j=i}^{i+k}x_j$
通过长期的观察，你总结出一支特别行动队的初始战斗力$x$将按如下经验公式修正为$x’：x’ = ax^2 + bx + c$，其中$a, b, c$是已知的系数（$a < 0$）
作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大，试求出这个最大和

例如，你有$4$名士兵，$x_1 = 2, x_2 = 2, x_3 = 3, x_4 = 4$，经验公式中的参数为$a = –1, b = 10, c = –20$
此时，最佳方案是将士兵组成$3$个特别行动队：第一队包含士兵$1$和士兵$2$，第二队包含士兵$3$，第三队包含士兵$4$
特别行动队的初始战斗力分别为$4, 3, 4$，修正后的战斗力分别为$4, 1, 4$，修正后的战斗力和为$9$，没有其它方案能使修正后的战斗力和更大

输入格式

第一行包含一个整数$n$，表示士兵的总数
第二行包含三个整数$a, b, c$，经验公式中各项的系数
第三行包含n 个用空格分隔的整数$x_1,x_2, \cdots, x_n$，分别表示编号为$1, 2, \cdots, n$的士兵的初始战斗力

输出格式

输出一行一个整数，代表最大的所有特别行动队战斗力之和

样例

样例输入

4 
-1 10 -20 
2 2 3 4

样例输出

数据范围与提示

对于$20%$的数据，$n \leqslant 10^3$
对于$50%$的数据，$n \leqslant 10^4$
对于$100%$的数据，$1 \leqslant n \leqslant 10^6，-5 \leqslant a \leqslant -1，-10^7 \leqslant b \leqslant 10^7，-10^7 \leqslant c \leqslant 10^7，1 \leqslant x_i \leqslant 100$

题解

显然是个DP
设$f_i$表示前$i$个人最大的所有特别行动队战斗力之和
假设战斗力的前缀和为$sum_i$
那么，我们可以得出$f_i=\min\limits_{1\leqslant j<i}{f_j+a(sum_i-sum_j)^2+b(sum_i-sum_j)+c}$
显然，这非常的像斜率优化的形式
假设$k$比$l$优
那么，$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$
$f_j-f_k+a(sum_j^2-sum_k^2)-b(sum_j-sum_k)<2asum_i(sum_j-sum_k)$
$\frac{f_j-f_k+a(sum_j^2-sum_k^2)-b(sum_j-sum_k)}{sum_j-sum_k}<2asum_i$
直接进行斜率优化
附上代码：

#include<cstdio>
long long n,a,b,c,l,r,x[1000010],sum[1000010],f[1000010],q[1000010];
double K(long long x,long long y)
{
    return 1.0*(f[x]-f[y]+a*(sum[x]*sum[x]-sum[y]*sum[y])-b*(sum[x]-sum[y]))/(sum[x]-sum[y]);
}
int main()
{
    scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
    for(int i=1;i<=n;i++) scanf("%lld",&x[i]),sum[i]=sum[i-1]+x[i];
    for(int i=1;i<=n;i++){
        while(l<r&&K(q[l],q[l+1])>2*a*sum[i]) l++;
        f[i]=f[q[l]]+a*(sum[i]-sum[q[l]])*(sum[i]-sum[q[l]])+b*(sum[i]-sum[q[l]])+c;
        while(l<r&&K(q[r],q[r-1])<K(q[r],i)) r--;
        q[++r]=i;
    }
    printf("%lld",f[n]);
}