正題

題目鏈接:https://www.luogu.com.cn/problem/CF311B

---

題目大意

$n$座山在一條線上，有$m$只貓，第$i$只從$t_i$開始在第$x_i$座山上游玩結束。

派$p$個人在不同時間從$1$走到$n$接走所有游玩結束的貓，求所有貓的最小等待時間。

---

解題思路

對于一只貓$i$，就是要求從$t_i?{\sum }_{j=1}^{x_i}{d}_j$時刻出發才可以接到。后文直接讓$t_i=t_i?{\sum }_{j=1}^{x_i}{d}_j$。排序后求一個前綴和$s$以方便后面計算。

那么我們肯定是直接接連續的一段$t_i$來接，我們設$f_{i,j}$表示到第$i$個人，接送了前$j$只貓時的最小等待時間和。那么有轉移方程$$f_i=min\{f_j+t_i(i?j)?(s_i?s_j)\}$$
$$f_i?s_i?t_{i}i=f_j?t_{i}j+s_j$$
設兩個$j,k(j>k)$中的$j$優于$k$
$$f_j?t_{i}j+s_j<f_k?t_{i}k+s_k$$
設$z_i=f_i+s_i$
$$z_j?z_k<t_i(j?k)$$
$$\frac{z_j?z_k}{j?k}<t_i$$

斜率優化即可，時間復雜度$O(np)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; ll n,m,p,d[N],t[N],f[101][N],s[N],z[N],q[N]; int main() {scanf("%lld%lld%lld",&n,&m,&p);for(ll i=2;i<=n;i++)scanf("%lld",&d[i]),d[i]+=d[i-1];for(ll i=1;i<=m;i++){ll x;scanf("%lld%lld",&x,&t[i]);t[i]-=d[x];}sort(t+1,t+1+m);memset(f,0x3f,sizeof(f));f[0][0]=0;for(ll i=1;i<=m;i++)s[i]=s[i-1]+t[i];for(ll i=1;i<=p;i++){ll l=1,r=1;q[1]=0;for(ll j=1;j<=m;j++)z[j]=f[i-1][j]+s[j];for(ll j=1;j<=m;j++){while(l<r&&z[q[l+1]]-z[q[l]]<=t[j]*(q[l+1]-q[l]))l++;f[i][j]=min(f[i-1][j],z[q[l]]-s[j]+(j-q[l])*t[j]); if(z[j]>=0x3f3f3f3f3f3f3f3fll)continue;while(l<r&&(z[j]-z[q[r]])*(q[r]-q[r-1])<=(z[q[r]]-z[q[r-1]])*(j-q[r]))r--;q[++r]=j;}}printf("%lld",f[p][m]);return 0; }

總結

以上是生活随笔為你收集整理的CF311B-Cats Transport【斜率优化dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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