方便计算,我们将点B放到最右边,所有点向左放,将最左边点的位置标为1。如样例,变为

1 3

21 3

1 2

6 5

而B在26的位置。

设\(dp_i\)为在点\(i\)设置车站,之前随便的最小花费;\(costs_i\)为所有\(i\)位置之前的人从出发点走到\(i\)的分数;\(pn_i\)为\(i\)位置及\(i\)位置之前的人数。

则在位置\([l+1,r]\)之间的人走到\(r\)的分数为\(costs_r-costs_l-pn_l\times(r-l)\)。

则状态转移方程为\(dp_i=min_{j=1}^{i-1}\{dp_j+costs_i-costs_j-pn_j\times(i-j)+m\}\)

将与\(j\)无关的项移出,展开,得\(dp_i=min_{j=1}^{i-1}\{dp_j-costs_j-pn_j\times i+pn_j\times j\}+costs_i+m\)

此时如果把内部变成直线解析式,\(k\)应等于\(-pn_j\),单调递减。

于是我们把式子变成:

\(dp_i=-max_{j=1}^{i-1}\{-dp_j+costs_j+pn_j\times i-pn_j\times j\}+costs_i+m\)

设\(k=pn_j\),\(b=-dp_j+costs_j-pn_j\times j\)

原式\(=ki+b\)

套上斜律优化即可。

code:

#include
    
     using namespace std;struct village{    int t,r;}v[40010];int n,m,d,nw,line[1000010],l,r;long long costs[1000010],pn[1000010],dp[1000010],k[1000010],b[1000010];bool cmp(village x,village y){    return x.t
     
      =(b[l3]-b[l1])*(k[l1]-k[l2]);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)scanf("%d%d",&v[i].t,&v[i].r),d=max(d,v[i].t+1);    for(int i=1;i<=n;i++)v[i].t=d-v[i].t;    sort(v+1,v+n+1,cmp);    nw=1;    for(int i=1;i<=d;i++){        pn[i]=pn[i-1];        while(v[nw].t==i)pn[i]+=v[nw++].r;        costs[i]=costs[i-1]+pn[i-1];    }    l=r=1;    for(int i=1;i<=d;i++){        while(l
      
       <=val(line[l+1],i))l++;        dp[i]=-val(line[l],i)+costs[i]+m;        k[i]=pn[i];        b[i]=costs[i]-pn[i]*i-dp[i];        while(l