正題

luogu-CF 311B

---

題目大意

有n個(gè)點(diǎn)，p個(gè)鏟屎官和m只貓
$d_i$表示i到i-1的距離
第i只貓?jiān)?span id="ze8trgl8bvbq" class="katex--inline">$t_i$這個(gè)時(shí)間$h_i$這個(gè)點(diǎn)開(kāi)始等待鏟屎官來(lái)接它走
鏟屎官會(huì)以一個(gè)單位時(shí)間走一個(gè)單位長(zhǎng)度的速度從第一個(gè)點(diǎn)向最后一個(gè)點(diǎn)走（不能停止），當(dāng)他走到點(diǎn)i時(shí)，若這里有貓?jiān)诘?#xff0c;那他就會(huì)接走他
現(xiàn)在讓你來(lái)安排各個(gè)鏟屎官的出發(fā)時(shí)間，使得每只貓等待時(shí)間之和最小

---

解題思路

設(shè)$f_{i,j}$為i個(gè)鏟屎官接前j只貓的最小等待時(shí)間之和

那么有：

$$\begin{array}{rl}{f}_{i,j}& =min\{f_{i?1,k}+\sum _{c=k+1}^j(t_j?t_c)\}\\ & =min\{f_{i?1,k}+\sum _{c=k+1}^j{t}_j?\sum _{c=k+1}^j{t}_c\}\\ & =min\{f_{i?1,k}+t[j]?(j?k)?sum{t}_j+sum{t}_k\}\\ & =min\{f_{i?1,k}+t_j?j?t_j?k?sum{t}_j+sum{t}_k\}\end{array}$$

對(duì)于決策點(diǎn)a、b，如果a>b，且a比b優(yōu)，那么有：

$$\begin{array}{rl}& \\ f_{i?1,a}+t_j?j?t_j?a?sum{t}_j+sum{t}_a& <f_{i?1,b}+t_j?j?t_j?b?sum{t}_j+sum{t}_b\\ f_{i?1,a}?t_j?a+sum{t}_a& <f_{i?1,b}?t_j?b+sum{t}_b\\ \frac{(f_{i?1,a}+sum{t}_a)?(f_{i?1,b}+sum{t}_b)}{a?b}& <t_j\end{array}$$

然后帶入模板即可

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll ww, n, m, c, xx, yy, w[100010], t[100010], l[100010], r[100010], sumt[100010], x[110][100010], f[110][100010]; int d[110][100010]; int main() {scanf("%lld%lld%lld", &ww, &n, &m);for (ll i = 2; i <= ww; ++i){scanf("%lld", &w[i]);w[i] += w[i - 1];}for (ll i = 1; i <= n; ++i){scanf("%lld%lld", &xx, &yy);t[i] = yy - w[xx];//計(jì)算出鏟屎官的出發(fā)時(shí)間}sort(t+1, t+1+n);for (ll i = 1; i <= n; ++i)sumt[i] = sumt[i - 1] + t[i];for (ll i = 1; i <= m; ++i)for (ll j = 1; j <= n; ++j){c = i - 1;while(l[c] < r[c] && x[c][d[c][l[c] + 1]] - x[c][d[c][l[c]]] < t[j] * (d[c][l[c] + 1] - d[c][l[c]])) l[c]++;f[i][j] = f[c][d[c][l[c]]] + t[j] * (j - d[c][l[c]]) - sumt[j] + sumt[d[c][l[c]]];x[i][j] = f[i][j] + sumt[j];while(l[i] < r[i] && (x[i][j]-x[i][d[i][r[i]]])*(d[i][r[i]]-d[i][r[i] - 1]) < (x[i][d[i][r[i]]]-x[i][d[i][r[i] - 1]])*(j-d[i][r[i]])) r[i]--;d[i][++r[i]] = j;}printf("%lld", f[m][n]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【斜率优化】Cats Transport（luogu-CF 311B）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。