Source:
http://acm.hdu.edu.cn/showproblem.php?pid=3507
题意：
分析：
dp[i] = min(dp[j] + (sum[i] - sum[j])^2) + m
然后斜率优化（题目似乎没有保证都是非负数，如果不是的话，不能用单调队列做。但是测a[i]<0的没有死循环，如果没被优化掉的话。。）
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxn = 1e5 * 5 + 100; 7 int n, m; 8 int a[maxn], q[maxn]; 9 long long dp[maxn], sum[maxn]; 10 11 inline long long x(int i, int j){ return sum[i] - sum[j]; } 12 inline long long y(int i, int j){ return dp[i] - dp[j] + sum[i] * sum[i] - sum[j] * sum[j]; } 13 inline long long cal(int i, int j){ 14 return dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]); 15 } 16 int main() 17 { 18 while(scanf("%d %d", &n, &m) != EOF){ 19 int head, tail; 20 head = tail = sum[0] = dp[0] = 0; 21 q[tail++] = 0; 22 for (int i = 1; i <= n; i++){ 23 scanf("%d", a+i); sum[i] = sum[i-1] + a[i]; 24 if (a[i] < 0) while(1); 25 //while(head + 1 < tail && cal(i, q[head+1]) < cal(i, q[head])) head ++; 26 while(head + 1 < tail && y(q[head], q[head+1]) > sum[i] * 2 * x(q[head], q[head+1])) head++; 27 dp[i] = cal(i, q[head]) + m; 28 while(head + 1 < tail && x(q[tail-1], q[tail-2]) * y(i, q[tail-1]) <= x(i, q[tail-1]) * y(q[tail-1], q[tail-2])) tail--; //想不明白为什么改成<就wa，=应该只有同向，但为什么要舍弃？。。 29 q[tail++] = i; 30 } 31 printf("%I64d\n", dp[n]); 32 } 33 return 0; 34 }