Picnic Cows HDU - 3045 斜率dp

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=4e5+50;
int q[N],l,r;
ll sum[N],val[N];
ll dp[N];
int n,m;
ll getdown(int j,int k) {
    return val[j+1]-val[k+1];
}

ll getup(int j,int k) {
    return (dp[j]-sum[j]+j*val[j+1])-(dp[k]-sum[k]+k*val[k+1]);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,0,sizeof dp);
        memset(sum,0,sizeof sum);
        memset(val,0,sizeof val);
        for(int i=1;i<=n;i++)
            scanf("%lld",&val[i]);
        sort(val+1,val+1+n);
        for(int i=1;i<=n;i++)
            sum[i]=sum[i-1]+val[i];
        l=r=0;
        q[0]=0;
        for(int i=2;i<=n;i++)
        {
            while(l<r && getup(q[l+1],q[l])<=getdown(q[l+1],q[l])*i)
                l++;
            int j=q[l];
            dp[i]=dp[j]+(sum[i]-sum[j])-(i-j)*val[j+1];
            j=i-m+1;
            if(j<m)
                continue;
            while(l<r && getup(q[r],q[r-1])*getdown(j,q[r-1])>= getup(j,q[r-1])*getdown(q[r],q[r-1])) 
                r--;
            q[++r]=j;
        }
        printf("%lld\n",dp[n]);
    }
}

Picnic Cows HDU - 3045 斜率dp

原文：https://www.cnblogs.com/QingyuYYYYY/p/12518034.html