斜率dp

斜率dp都不大好写啊，细节的边界处理感觉好麻烦啊。
这里我们很容易就总结出状态和状态转移方程了。
我们首先从小到大排序(在斜率dp中排序很重要，有利于保持决策的单调性)
dp[i] 表示到第i个点为止的最小花费。
dp[i] = min(dp[j-1]+sum[i]-sum[j]-(i-j+1)a[j])
注意范围t+1<=j<=i-t+1
那么我们就对这个公式进行斜率dp的优化就行了，把他变为O(n)
但是要注意的是起始的初始状态。
如果i<t的时候怎么办，很显然这时是不可能的。
那么当i<2t时怎么办？很显然这时我们必须一起打包买走的。
处理好初始情况，我们就可以解题了

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
const int max_n = 4e5+100;
int n,t;
typedef __int64 ll;
const ll inf = 1e18;
ll a[max_n],sum[max_n],dp[max_n];

bool check(int p1,int p2,int k){
    ll x1 = a[p1],y1 = dp[p1-1]-sum[p1-1]+(p1-1)*a[p1];
    ll x2 = a[p2],y2 = dp[p2-1]-sum[p2-1]+(p2-1)*a[p2];
    return (y2-y1)<=k*(x2-x1);
}
bool check2(int p1,int p2,int p3){
    ll x1 = a[p1],y1 = dp[p1-1]-sum[p1-1]+(p1-1)*a[p1];
    ll x2 = a[p2],y2 = dp[p2-1]-sum[p2-1]+(p2-1)*a[p2];
    ll x3 = a[p3],y3 = dp[p3-1]-sum[p3-1]+(p3-1)*a[p3];
    return (y2-y1)*(x3-x2)>=(y3-y2)*(x2-x1);
}

int main(){
    while (~scanf("%d %d",&n,&t)){
        for (int i=1;i<=n;++i)scanf("%lld",&a[i]);
        sort(a+1,a+1+n);
        for (int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
        deque<int> que;
        for (int i=t;i<2*t&&i<=n;++i)dp[i]=sum[i]-a[1]*i;
        for (int i=2*t;i<=n;++i){
            int k = i;
            while (que.size()>=2&&check2(que[que.size()-2],que[que.size()-1],i+1-t))que.pop_back();
            que.push_back(i-t+1);
            while (que.size()>=2&&check(que[0],que[1],k))que.pop_front();
            int j = que.front();
            dp[i]=dp[j-1]+sum[i]-sum[j-1]-(i-j+1)*a[j];
        }
        printf("%lld\n",dp[n]);
    }
}