n个数，可进行把一个数减小的操作，代价为减小的值。现求使数列任意一个数都存在至少k-1个数和他相同，问操作的最小代价。
可以先考虑最小的数，由于只能减，所以必须得至少k-1个数减为最小数，贪心策略：从小到大从最小数开始的后面至少k-1个数必须减为他自己这一块代价才最小。很好想，如果里面有一个不选，那必须有一个更大的数下降，并且不选的这个数在之后也使后面另一块的数减的更多，所以总是把连续的至少k个数减为开头最小的那个数。那就是数列上划分块的dp，$f[i]$是到$i$时最小代价。
$f[i]=min \{ f[j]+sum[i]-sum[j]-(i-j)*a[j+1] \} $ $ 0<=j<=i-k且j∉[1,k-1]$
然后拆开就是一个常规的斜率优化了。注意一下开头k-1个是不能作为决策点的（因为无解），不要进队。0是可以进队的。
没了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+c-'',c=getchar();return f?x=-x:x;
}
const int N=+;
ll f[N],sum[N];
int a[N],q[N],T,n,k,l,r;
inline ll x(int j){return (ll)a[j+];}
inline ll y(int j){return f[j]+j*1ll*a[j+]-sum[j];} int main(){//freopen("test.in","r",stdin);//freopen("tmp.out","w",stdout);
read(T);while(T--){
read(n),read(k);l=,r=;
for(register int i=;i<=n;++i)sum[i]=read(a[i])+sum[i-];
for(register int i=k;i<=n;++i){
if(i==k||i>=(k<<)){
while(l<r&&(y(i-k)-y(q[r]))*(x(q[r])-x(q[r-]))<=(y(q[r])-y(q[r-]))*(x(i-k)-x(q[r])))--r;
q[++r]=i-k;
}
while(l<r&&y(q[l+])-y(q[l])<=1ll*i*(x(q[l+])-x(q[l])))++l;
f[i]=f[q[l]]+sum[i]-sum[q[l]]-(i-q[l])*1ll*a[q[l]+];
}
printf("%lld\n",f[n]);
}
return ;
}