LibreOJ 10190.「APIO2010」特别行动队

首先列出朴素的转移方程 fi=max0j<i(fj+a(sumisumj)2+b(sumisumj)+c)f_i = \max\limits_{0 \le j < i} (f_j + a (sum_i - sum_j)^2 + b (sum_i - sum_j) + c)
其中 sumi=j=1ixjsum_i = \sum\limits_{j = 1}^i x_j

对于 0k<j<i0 \le k < j < i,假设决策 jj 优于决策 kk,有

维护一只上凸包即可~

代码:

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
#include <cstdio>
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]);
}

arknights