题意：给定一个不下降数列，一个K，将数列分成若干段，每段的数字个数不小于K，每段的代价是这段内每个数字减去这段中最小数字之和。求一种分法使得总代价最小？
思路:F[i]表示到i的最小代价。f[i]=min(f[j]+sum[i]-sum[j]-(i-j)*a[j+1]);(i-j>=K)
对于j1,j2,j1<j2且j2更优得
f[j1]+sum[i]-sum[j1]-(i-j1)*a[j1+1]>f[j2]+sum[i]-sum[j2]-(i-j2)*a[j2+1]
得到:
f[j1]-sum[j1]+a[j1+1]*j1)-(f[j2]-sum[j2]+a[j2+1]*j2)>=i*(a[j1+1]-a[j2+1])
可以用单调队列维护.
由于每一层需要K个，所以我们延迟入队的时间.
1 #include<algorithm> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 #define ll long long 7 long long f[1000005],sum[1000005],a[1000005]; 8 int c[1000005]; 9 int n,K,T; 10 ll G(int j,int k){ 11 return f[j]-sum[j]+j*a[j+1]-(f[k]-sum[k]+k*a[k+1]); 12 } 13 ll S(int j,int k){ 14 return a[j+1]-a[k+1]; 15 } 16 int main(){ 17 scanf("%d",&T); 18 while (T--){ 19 scanf("%d%d",&n,&K); 20 sum[0]=0; 21 for (int i=1;i<=n;i++) scanf("%I64d",&a[i]); 22 for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i],f[i]=0; 23 int h=0,t=0; 24 c[t++]=0;f[0]=0; 25 for (int i=1;i<=n;i++){ 26 while (h<t-1&&G(c[h],c[h+1])>=i*S(c[h],c[h+1])) h++; 27 f[i]=(ll)f[c[h]]+sum[i]-sum[c[h]]-(i-c[h])*a[c[h]+1]; 28 if (i>=2*K-1) c[t++]=i-K+1; 29 for (int j=t-2;j>h;j--){ 30 int x=c[j-1],y=c[j],z=c[j+1]; 31 if (G(x,y)*S(y,z)>=G(y,z)*S(x,y)) c[j]=c[--t]; 32 else break; 33 } 34 } 35 printf("%I64d ",f[n]); 36 } 37 }