HDU 3507 斜率优化 DP Print Article

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int maxn = 500000 + 10;
 9 int d[maxn], Q[maxn], sum[maxn];
10 
11 int head, tail;
12 int n, M;
13 
14 int inline dx(int i, int j)
15 {
16     return sum[j] - sum[i];
17 }
18 
19 int inline dy(int i, int j)
20 {
21     return d[j] + (sum[j]*sum[j]) - d[i] - (sum[i]*sum[i]);
22 }
23 
24 int inline DP(int i, int j)
25 {
26     return d[i] + (sum[j]-sum[i])*(sum[j]-sum[i]) + M;
27 }
28 
29 int main()
30 {
31     while(scanf("%d%d", &n, &M) == 2 && n)
32     {
33         for(int i = 1; i <= n; i++) scanf("%d", sum + i);
34         for(int i = 2; i <= n; i++) sum[i] += sum[i - 1];
35 
36         head = tail = 0;
37         Q[tail++] = 0;
38         for(int i = 1; i <= n; i++)
39         {
40             while(head + 1 < tail && dy(Q[head], Q[head + 1]) <= 2 * sum[i] * dx(Q[head], Q[head + 1])) head++;
41             d[i] = DP(Q[head], i);
42             while(head + 1 < tail && dy(Q[tail-1], i) * dx(Q[tail-2], Q[tail-1]) <= dy(Q[tail-2], Q[tail-1]) * dx(Q[tail-1], i)) tail--;
43             Q[tail++] = i;
44         }
45 
46         printf("%d
", d[n]);
47     }
48 
49     return 0;
50 }
代码君