题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1911
Description
Input
Output
斜率优化DP
教主的题解：http://www.cnblogs.com/JSZX11556/p/4811459.html
我也懒得写下去了……
1.10晚 补题解：令 s[i] 为 x[i] 的前缀和，f[i] = min{ f[j] + A * ( s[i] - s[j] ) ^ 2 + B * ( s[i] - s[j] ) + C }， j < i
若 j 优于 k，j > k，则有 f[j] - f[k] + A * ( s[j] ^ 2 - s[k] ^ 2 ) >= ( 2 * A * s[i] + B ) * ( s[j] - s[k] )
将 s[j] - s[k] 移到左边，得斜率单调递减，用单调队列维护一个下凸函数即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #define rep(i,l,r) for(int i=l; i<=r; i++) 6 #define clr(x,y) memset(x,y,sizeof(x)) 7 using namespace std; 8 typedef long long ll; 9 const int maxn = 1000010; 10 ll n,A,B,C,head,tail,f[maxn],q[maxn],s[maxn]; 11 inline ll read(){ 12 ll ans = 0, f = 1; 13 char c = getchar(); 14 for(; !isdigit(c); c = getchar()) 15 if (c == '-') f = -1; 16 for(; isdigit(c); c = getchar()) 17 ans = ans * 10 + c - '0'; 18 return ans * f; 19 } 20 inline ll calc(int x){ 21 return f[x] + A * s[x] * s[x]; 22 } 23 inline ll get(int i,int j){ 24 return f[j] + A * (s[i] - s[j]) * (s[i] - s[j]) + B * (s[i] - s[j]) + C; 25 } 26 int main(){ 27 n = read(); A = read(); B = read(); C = read(); 28 rep(i,1,n) s[i] = s[i-1] + read(); 29 head = tail = f[0] = q[0] = 0; 30 rep(i,1,n){ 31 while (head < tail && calc(q[head+1]) - calc(q[head]) >= (2 * A * s[i] + B) * (s[q[head+1]] - s[q[head]])) head++; 32 f[i] = get(i,q[head]); 33 while (head < tail && (calc(q[tail]) - calc(q[tail-1])) * (s[i] - s[q[tail]]) <= (calc(i) - calc(q[tail])) * (s[q[tail]] - s[q[tail-1]])) tail--; 34 q[++tail] = i; 35 } 36 printf("%lld ",f[n]); 37 return 0; 38 }