方便計算,我們將點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<bits/stdc++.h> 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<y.t; } long long val(int l1,int x){return k[l1]*x+b[l1]; } bool cov(int l1,int l2,int l3){return (b[l2]-b[l1])*(k[l1]-k[l3])>=(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<r&&val(line[l],i)<=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<r&&cov(i,line[r-1],line[r]))r--;line[++r]=i;}printf("%lld",dp[d]-m);return 0; }

轉載于:https://www.cnblogs.com/xryjr233/p/BZOJ2153.html

總結

以上是生活随笔為你收集整理的[2018.12.9]BZOJ2153 设计铁路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。