题解 P3628 【[APIO2010]特别行动队 】
题目大意
给你一个序列， 将这个序列分成若干段， 每一段的贡献为 \(ax ^ 2 + bx + c\)(x 为 这一段的权值之和)
具体思路
50pts
考虑Dp， 设\(Dp_i\)为前i个数分成若干段的最大收益, 则\(Dp[i] = max(Dp[j-1] + Cost_{i,j})\quad(j <= i)\)
现在想\(cost\) 函数怎么求得
设\(Sum[i]\) 为 i 的前缀和， 则\(cost_{i, j} = a(Sum[i] – Sum[j]) ^ 2 + b (Sum[i] – Sum[j-1]) + c\) 可以\(O(1)\) 求得
100pts
想一想如何优化这个转移， 发现j每次都是从1 至 n , 考虑进行斜率优化
不妨设 x > y 且 ｘ的转移优于ｙ
则\(Dp[x] + a(Sum[i] – Sum[x]) ^ 2 + b (Sum[i] – Sum[x]) + c > Dp[y]+ a(Sum[i] – Sum[y]) ^ 2 + b (Sum[i] – Sum[y]) + c\)
\(\Leftrightarrow Dp[i] + a(Sum[i] ^ 2 + Sum[x] ^ 2 – 2 * Sum[i] * Sum[x]) + b(Sum[i] – Sum[x]) + c > Dp[y] + a(Sum[i] ^ 2 + Sum[y] ^ 2 – 2 * Sum[i] * Sum[x]) + b(Sum[i] – Sum[y]) + c\)
\(\Leftrightarrow Dp[i] + aSum[i] ^ 2 + aSum[x] ^ 2 – 2 * a * Sum[i] * Sum[x] + b Sum[i] – bSum[x ] + c > Dp[y] + a * Sum[y] ^ 2 + a * Sum[y] ^ 2 – 2aSum[i] * Sum[x] + bSum[i] – bSum[y] + c\)
移项、合并同类项得
\(Dp[x] – Dp[y] + a(Sum[x ] ^ 2 – Sum[y] ^ 2) – b(Sum[x] – Sum[y]) > 2aSum[i](Sum[x] – Sum[y])\)
\(\Leftrightarrow \frac{Dp[x] – Dp[y] + a(Sun[x] ^ 2 – Sum[y] ^ 2) – b(Sum[x] – Sum[y])}{(Sum[x] – Sum[y])} > 2aSum[i]\)
\(\Leftrightarrow \frac{Dp[x] + aSum[x] ^ 2 + bSum[x] – Dp[y] – aSum[y]^2 – bSum[y]}{(Sum[x] – Sum[y])} > 2aSum[i]\)
注意：由于题面说\(a < 0 \) 所以如果要将ａ除过去要将符号转向
不难发现左式为一个直线的点斜式，故令其为Slope(x, y) 要满足决策单调性即Slope满足单调性， 用单调队列维护即可
代码实现
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <cstdio>
template<class T>
inline void read(T &a){
T s = 0, w = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-') w = -1; c = getchar();}
while(c >= '0' && c <= '9') {s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();}
a = s * w;
}
#define maxn 1000010
static int n,s[maxn],l,r,q[maxn];
static long long a,b,c,dp[maxn];
#define A(x) (dp[x] + a * s[x] * s[x] - b * s[x])
#define P(x) (s[i] - s[x])
inline double slope(register int x, register int y){
return 1.0 * (A(x) - A(y)) / ((s[x] - s[y]));
}
signed main(){
read(n), read(a), read(b), read(c);
for (register int i = 1; i <= n; i++){
int x;
read(x);
s[i] = s[i-1] + x;
}
for (register int i = 1; i <= n; i++){
while(l < r && slope(q[l + 1], q[l]) > 2*a*s[i]) l++;
dp[i] = dp[q[l]] + a * P(q[l]) * P(q[l]) + b * P(q[l]) + c;
while(l < r && slope(q[r], q[r-1]) < slope(i, q[r])) r--;
q[++r] = i;
}
printf("%lld", dp[n]);
return 0;
}