POJ 3709 K-Anonymous Sequence - 斜率优化dp

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define rd read()
 5 #define rep(i,a,b) for( int i = (a); i <= (b); ++i)
 6 #define per(i,a,b) for( int i = (a); i >= (b); --i)
 7 using namespace std;
 8 typedef long long ll;
 9 
10 const int N = 1e6;
11 const ll inf = 1LL << 61;
12 
13 ll sum[N], f[N], q[N], d[N];
14 int n, T, k;
15 
16 int read() {
17     int X = 0, p = 1; char c = getchar();
18     for(; c > ‘9‘ || c < ‘0‘; c = getchar()) if( c == ‘-‘) p = -1;
19     for(; c >= ‘0‘ && c <= ‘9‘; c = getchar()) X = X * 10 + c - ‘0‘;
20     return X * p;
21 }
22 
23 double calc(int a, int b) {
24     double y = f[b] + b * d[b + 1] - sum[b] - f[a] - a * d[a + 1] + sum[a];
25     double x = d[b + 1] - d[a + 1];
26     if(!x && !y) return inf;
27     return y / x;
28 }
29 
30 int main()
31 {
32     T = rd;
33     for(; T; T--) {
34         n = rd; k = rd;
35         rep(i, 1, n) d[i] = rd, sum[i] = sum[i - 1] + d[i];
36         rep(i, k, n) f[i] = sum[i] - i * d[1];
37         rep(i, 0, k - 1) f[i] = inf;
38         int l = 1, r = 1;
39         q[1] = k;
40         rep(i, 2 * k, n) {
41             while(l < r && calc(q[l], q[l + 1]) <= i) l++;
42             f[i] = min(f[i], f[q[l]] + sum[i] - sum[q[l]] - (i - q[l]) * d[q[l] + 1]);
43             while(l < r && calc(q[r - 1], q[r]) >= calc(q[r], i - k + 1)) r--;
44             q[++r] = i - k + 1;
45         }
46         printf("%lld\n", f[n]);
47     }
48 }