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

描述

给定一个数列 $a$， 分成若干段，每段至少有$k$个数， 将每段中的数减少至所有数都相同， 求最小的变化量

题解

易得到状态转移方程 $F_i = \min(F_j  + sum_i – sum_j – (i – j ) \times a_(j+1) ) $ $ 0 <= j <= i – k$。

把只含$j$ 放在一边， 其他的放在另一边得到：$F_j + j \times a_(j+1)  – sum_j =  i \times a_(j+1)  F_i – sum_i$

然后就可以愉快地套上斜率优化的板子了QuQ

还有这道题我用叉积挂了唔， 数列$a_i$是不严格递增的，点重合就挂了（也有可能是我自己打挂了

代码

 #include<cstring>
 #include<cstdio>
 #include<algorithm>
 #define rd read()
 #define rep(i,a,b) for( int i = (a); i <= (b); ++i)
 #define per(i,a,b) for( int i = (a); i >= (b); --i)
 using namespace std;
 typedef long long ll; const int N = 1e6;
 const ll inf = 1LL << ; ll sum[N], f[N], q[N], d[N];
 int n, T, k; int read() {
     int X = , p = ; char c = getchar();
     for(; c > '' || c < ''; c = getchar()) if( c == '-') p = -;
     for(; c >= '' && c <= ''; c = getchar()) X = X *  + c - '';
     return X * p;
 } double calc(int a, int b) {
     double y = f[b] + b * d[b + ] - sum[b] - f[a] - a * d[a + ] + sum[a];
     double x = d[b + ] - d[a + ];
     if(!x && !y) return inf;
     return y / x;
 } int main()
 {
     T = rd;
     for(; T; T--) {
         n = rd; k = rd;
         rep(i, , n) d[i] = rd, sum[i] = sum[i - ] + d[i];
         rep(i, k, n) f[i] = sum[i] - i * d[];
         rep(i, , k - ) f[i] = inf;
         int l = , r = ;
         q[] = k;
         rep(i,  * k, n) {
             while(l < r && calc(q[l], q[l + ]) <= i) l++;
             f[i] = min(f[i], f[q[l]] + sum[i] - sum[q[l]] - (i - q[l]) * d[q[l] + ]);
             while(l < r && calc(q[r - ], q[r]) >= calc(q[r], i - k + )) r--;
             q[++r] = i - k + ;
         }
         printf("%lld\n", f[n]);
     }
 }