#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define MAXN 500005using namespace std;typedef long long LL;LL f[MAXN],sum[MAXN];LL num[MAXN];#define FZ(p)(f[p]-sum[p]+p*num[p+1])LL i,p;LL que[MAXN],tail,head;LL n,m,j;bool turnup(LL p1,LL p2,LL p3) { LL y1=FZ(p1),x1=num[p1+1],y2=FZ(p2), x2=num[p2+1], y3=FZ(p3), x3=num[p3+1]; if((x2-x3)*(y1-y2)>(x1-x2)*(y2-y3))return 1; else return 0;} LL nn,ii,trmp;int main(){ scanf("%I64d",&nn); for(ii=1;ii<=nn;ii++) { scanf("%I64d%I64d",&n,&m); for(int i=1;i<=n;i++) { scanf("%I64d",&num[i]); sum[i]=sum[i-1]+num[i];; } f[0]=0; head=tail=1; que[tail++]=0; for(int i=1;i<=n;i++) { while(head<tail-1&&FZ(que[head+1])-FZ(que[head])<i*(num[que[head+1]+1]-num[que[head]+1])) head++; LL k=que[head]; f[i]=f[k]+sum[i]-sum[k]-num[k+1]*(i-k); if(i>=m*2-1) { trmp =i-m+1; while(head<tail-1&&turnup(i,que[tail-1],que[tail-2])==0) tail--; que[tail++]=trmp; } } printf("%I64d\n",f[n]); }}
转载于:https://www.cnblogs.com/Lamboofhome/p/11600752.html
相关资源：JAVA上百实例源码以及开源项目