首先列出朴素的转移方程 \(f_i = \max\limits_{0 \le j < i} (f_j + a (sum_i - sum_j)^2 + b (sum_i - sum_j) + c)\)。
其中 \(sum_i = \sum\limits_{j = 1}^i x_j\)。
对于 \(0 \le k < j < i\)，假设决策 \(j\) 优于决策 \(k\)，有 \[\begin{align*} f_j + a (sum_i - sum_j) ^ 2 + b (sum_i - sum_j) + c & \ge f_k + a (sum_i - sum_k)^2 + b (sum_i - sum_k) + c \\ f_j - 2a \cdot sum_i sum_j + a \cdot sum_j^2 - b \cdot sum_j & \ge f_k - 2a \cdot sum_i sum_k + a \cdot sum_k^2 - b \cdot sum_k \\ (f_j + a \cdot sum_j^2 - b \cdot sum_j) - (f_k + a \cdot sum_k^2 - b \cdot sum_k) & \ge 2a \cdot sum_i (sum_j - sum_k) \\ \dfrac{(f_j + a \cdot sum_j^2 - b \cdot sum_j) - (f_k + a \cdot sum_k^2 - b \cdot sum_k)}{sum_j - sum_k} & \ge 2a \cdot sum_i \end{align*}\]
维护一只上凸包即可~
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
const int N = 1e6;
int n,a,b,c;
int q[N + 5],head,tail;
long long f[N + 5],sum[N + 5];
inline double slope(int x,int y)
{
return (double)(f[x] - f[y] + (sum[x] * sum[x] - sum[y] * sum[y]) * a - (sum[x] - sum[y]) * b) / (sum[x] - sum[y]);
}
int main()
{
scanf("%d%d%d%d",&n,&a,&b,&c);
for(register int i = 1;i <= n;++i)
scanf("%lld",sum + i),sum[i] += sum[i - 1];
q[head = tail = 1] = 0;
for(register int i = 1;i <= n;++i)
{
for(;head < tail && slope(q[head],q[head + 1]) >= 2 * a * sum[i];++head);
f[i] = f[q[head]] + a * (sum[i] - sum[q[head]]) * (sum[i] - sum[q[head]]) + b * (sum[i] - sum[q[head]]) + c;
for(;head < tail && slope(q[tail - 1],q[tail]) <= slope(q[tail],i);--tail);
q[++tail] = i;
}
printf("%lld\n",f[n]);
}