https://www.luogu.org/problem/P2365

分析：

f[i]表示前i个分组后的最小费用

f[i]=min(f[j]+t[i](c[i]-c[j])+s(c[n]-c[j]));

前j个 i~j的答案 因为分了一组，所以在此之后的组肯定至少有一个等待的s

c是费用前缀和数组

t是时间

直接把min甩掉

\[f[i]=f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j])\]

\[f[j]=f[i]-t[i]*(c[i]-c[j])-s*(c[n]-c[j])\]

\[f[j]=f[i]-t[i]*c[i]+t[i]*c[j]-s*c[n]+s*c[j]\]

\(f[j]=(s+t[i])*c[j]+f[i]-t[i]*c[i]-s*c[n]\)
y = k * x + b

因为j已知，所以一次函数中的y和x都要是j为下标的

因此推出上述式子

发现我们要求的是f[i]最小

那么就是b最小

(c[j],f[j])

然后直线过每个点找最小的截距

上凸放弃凸点

下凸可能是凸点

相邻的斜率单调递增的

所以最有解的点左斜率小于k右斜率大于k

单调队列，所以只要考虑右斜率

code:

#include<cstdio>
#include<deque>
using namespace std;
deque<long long>q;
long long t[5005],f[5005];
long long h[5005];
long long dp[5005];//dp[i]表示在i分组完毕后的答案 
int main()
{
    freopen("batch.in","r",stdin);
    freopen("batch.out","w",stdout); 
    long long n,s;
    scanf("%lld%lld",&n,&s);
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld%lld",&t[i],&f[i]);
        t[i]+=t[i-1];//计算时间前缀和 
    }
    for(long long i=n;i>=1;i--)
    {
        h[i]=h[i+1]+f[i];//费用后缀，逆推准备 
    }
    q.push_back(n+1);//初始化，此双端队列基本保证单调 
    for(long long i=n;i>=1;i--)//倒推  
    {
        //保证队列中至少有两个数，且(q[0],q[1])的组合结果比元两者组合的答案大 
        while(q.size()&&q.size()!=1&&h[i]*(t[q[0]-1]-t[q[1]-1])>=dp[q[1]]-dp[q[0]])
        {
            q.pop_front();//就把q[0]弹出去，因为Q【0】在这个组合中会拖后腿 
        }
        //将i加入i~q[0]和q[0]至n 
        dp[i]=dp[q[0]]+h[i]*(s+t[q[0]-1]-t[i-1]); 
        while(q.size()&&q.size()!=1) 
        {
            long long len=q.size();
            //(i,len-1)和（len-1,len-2)比较 
            if((dp[i]-dp[q[len-1]])*(t[q[len-2]-1]-t[q[len-1]-1])<=(dp[q[len-1]]-dp[q[len-2]])*(t[q[len-1]-1]-t[i-1]))
            {//算斜率是哪凸 
                q.pop_back();
            }
            else
            {
                break;
            }
        }
        q.push_back(i);  
    }
    printf("%lld\n",dp[1]); 
    return 0;
}