hdu 3045 斜率优化DP

思路：dp[i]=dp[j]+sum[i]-sum[j]-(i-j)*num[j+1];

然后就是比较斜率。

注意的时这里j+t<=i；

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define Maxn 400010
#define LL __int64
using namespace std;
LL num[Maxn],sum[Maxn],dp[Maxn];
int que[Maxn*10];
LL Getleft(int j,int k)
{
    return dp[j]-sum[j]+j*num[j+1]-(dp[k]-sum[k]+k*num[k+1]);
}
LL Getright(int j,int k)
{
    return num[j+1]-num[k+1];
}
int main()
{
    int n,t,head,rear;
    LL i,j;
    while(scanf("%d%d",&n,&t)!=EOF){
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++){
            scanf("%I64d",num+i);
        }
        sort(num+1,num+n+1);
        for(i=1;i<=n;i++){
            sum[i]=num[i]+sum[i-1];
        }
        head=1,rear=0;
        que[++rear]=0;
        for(i=t;i<=n;i++){
            j=i-t+1;
            while(head<rear&&Getleft(que[head+1],que[head])<=Getright(que[head+1],que[head])*i){
                head++;
            }
            dp[i]=dp[que[head]]+sum[i]-sum[que[head]]-(i-que[head])*num[que[head]+1];
            while(head<rear&&j>=t&&Getleft(j,que[rear])*Getright(que[rear],que[rear-1])<=Getleft(que[rear],que[rear-1])*Getright(j,que[rear])){
                rear--;
            }
            if(j>=t)
            que[++rear]=j;
        }
        printf("%I64d
",dp[n]);
    }
    return 0;
}