$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

$\begin{aligned}因为\ f_i & = \min\{f_j+t_i\cdot (c_i-c_j)+s\cdot (c_n-c_j)\} \\\\ & = \min\{f_j-c_j\cdot (t_i+s)+t_i\cdot c_i+s\cdot c_n\} \end{aligned}$

$所以\ f_j=(t_i+s)\cdot c_j+f_i-t_i\cdot c_i-s\cdot c_n\Rightarrow y=kx+b$

$则\ y=f_j,\ x=c_j,\ k=t_i+s,\ b=f_i-t_i\cdot c_i-s\cdot c_n$

$要使\ f_i\ 最小，即让\ \dfrac{f_j}{c_j}\ 最小$

$将队头所有小于\ k\ 的斜率删掉：\dfrac{f_{q_{hh+1}}-f_{q_{hh}}}{c_{q_{hh+1}}-c_{q_{hh}}}\le t_i+s，队头\ f_{q_{hh}}\ 即\ f_j\ 可以使\ f_i\ 最小$

$将队尾不符合条件的\ k\ 删掉：\dfrac{f_{q_{tt}}-f_{q_{tt-1}}}{c_{q_{tt}}-c_{q_{tt-1}}}\ge \dfrac{f_i-f_{q_{tt}}}{c_i-c_{q_{tt}}}$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 300010;

int n,s;
int q[N];
LL t[N],c[N];
LL f[N];

int main()
{
    cin>>n>>s;

    for(int i=1;i<=n;i++)
    {
        cin>>t[i]>>c[i];
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }

    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        while(hh<tt&&f[q[hh+1]]-f[q[hh]]<=(t[i]+s)*(c[q[hh+1]]-c[q[hh]])) hh++; //将所有小于等于斜率 k 的斜率删掉
        int j=q[hh];
        f[i]=f[j]-c[j]*(t[i]+s)+t[i]*c[i]+s*c[n];
        while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=(f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]])) tt--; //将队尾不符合条件的斜率删掉
        q[++tt]=i;
    }

    cout<<f[n]<<endl;

    return 0;
}