0x60 斜率优化DP

任务安排

题意：

$n$ 个任务排成序列，将任务分批。执行第 $i$ 个任务所需要时间 tit_iti​。每批任务开始前，需要 $s$ 时间，一批任务所需要的时间为 $s$ 加上每个任务需要时间。同一批任务的完成时间为该批所有任务执行完成的时间。每个任务的代价为完成时刻与费用系数 cic_ici​ 的成绩。

询问最小总费用。

数据规模：1≤n≤5000,1≤ti,ci≤100,0≤s≤501 \\le n \\le 5000, 1 \\le t_i, c_i \\le 100, 0 \\le s \\le 501≤n≤5000,1≤ti​,ci​≤100,0≤s≤50

解析：

设计状态。第一维是前 $i$ 个任务，在状态转移时需要知道前边有多少分组，所以增加一维 $j$，表示是第 $j$ 组任务。

所以 fi,jf_{i,j}fi,j​ 为前 $i$ 个任务，分成 $j$ 组的最小代价。

状态转移：fi,j=min⁡{fk,j−1+(S×j+∑u=1iti)×∑u=k+1ici}f_{i,j} = \\min\\Big\\{f_{k,j-1}+(S\\times j+\\sum\\limits_{u = 1}\\limits^it_i) \\times \\sum\\limits_{u = k+1}\\limits^ic_i\\Big\\}fi,j​=min{fk,j−1​+(S×j+u=1∑i​ti​)×u=k+1∑i​ci​}

用前缀和优化后时间复杂度为 O(n3)O(n^3)O(n3)。

增加一维状态 $j$ 是为了计算 $s$ 对当前组的贡献。如果当前组为 $[l,r]$ ，影响到的任务为 $[l,n]$。采用 费用提前计算 的思想，将对后续任务的代价加到当前状态上。

fi=min⁡{fj+s×∑k=j+1nck+∑k=1itk×∑k=j+1ick}f_i = \\min\\Big\\{f_j+s\\times \\sum\\limits_{k = j+1}\\limits^nc_k+\\sum\\limits_{k=1}\\limits^{i}t_k\\times \\sum\\limits_{k = j+1}\\limits^{i}c_k\\Big\\}fi​=min{fj​+s×k=j+1∑n​ck​+k=1∑i​tk​×k=j+1∑i​ck​}

前缀和优化：fi=min⁡{fj+s×(scn−scj)+sti×(sci−scj)}f_i = \\min\\Big\\{f_j+s\\times(sc_n-sc_j)+st_i\\times(sc_i-sc_j)\\Big\\}fi​=min{fj​+s×(scn​−scj​)+sti​×(sci​−scj​)}

通过费用提前计算的思想简化状态。时间复杂度为 O(n2)O(n^2)O(n2)

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;ll sumt[maxn], sumc[maxn], f[maxn];
ll n, s;int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> s;for(int i = 1; i <= n; i++){cin >> sumt[i] >> sumc[i];sumt[i] += sumt[i-1];sumc[i] += sumc[i-1];}memset(f, INF, sizeof(f));f[0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j < i; j++){f[i] = min(f[i], f[j]+sumt[i] * (sumc[i]-sumc[j]) + s * (sumc[n]-sumc[j]));}}cout << f[n] << endl;return 0;
}

任务安排2

题意：

完全同上题。

数据规模：1≤n≤3×105,1≤ti,ci≤512,0≤s≤5121 \\le n \\le 3\\times 10^5, 1 \\le t_i, c_i \\le 512, 0 \\le s \\le 5121≤n≤3×105,1≤ti​,ci​≤512,0≤s≤512

解析：

状态转移方程：fi=min⁡{fj+s×(scn−scj)+sti×(sci−scj)}f_i = \\min\\Big\\{f_j+s\\times(sc_n-sc_j)+st_i\\times(sc_i-sc_j)\\Big\\}fi​=min{fj​+s×(scn​−scj​)+sti​×(sci​−scj​)}

去掉min：fi=fj+s×(scn−scj)+sti×(sci−scj)f_i = f_j+s\\times(sc_n-sc_j)+st_i\\times(sc_i-sc_j)fi​=fj​+s×(scn​−scj​)+sti​×(sci​−scj​)

右侧的项分为三类：只与 $i$ 有关，只与 $j$ 有关，与 $i,j$ 均有关。将同一类的放在一起：fi=(sti×sci+s×scn)+fj−scj×(s+sti)f_i = (st_i\\times sc_i+s\\times sc_n)+f_j-sc_j\\times (s+st_i)fi​=(sti​×sci​+s×scn​)+fj​−scj​×(s+sti​)。

进行移项，形如 $y=kx+b$ 的形式

将$func(i)\times func(j)$ 看成 $k\times x$ ，fif_ifi​ 的项出现在 $b$ 中，$func(j)$ 的项在 $y$ 中。

如果 $x$ 的表达式单调递减，等式两边同乘-1，变为单调递增。

y=fjy = f_jy=fj​，x=scjx = sc_jx=scj​，k=s+stik = s+st_ik=s+sti​，b=fi−(sti×sci+s×scn)b = f_i-(st_i\\times sc_i+s\\times sc_n)b=fi​−(sti​×sci​+s×scn​)。

设 j1,j2(j1≤j2)j_1,j_2(j_1 \\le j_2)j1​,j2​(j1​≤j2​) 是 $i$ 的两个合法决策点，且满足 j2j_2j2​ 优于 j1j_1j1​。

即：fj1−scj1×(s+sti)≥fj2−scj2×(s+sti)f_{j_1}-sc_{j_1}\\times (s+st_i) \\ge f_{j_2}-sc_{j_2}\\times (s+st_i)fj1​​−scj1​​×(s+sti​)≥fj2​​−scj2​​×(s+sti​)

因为 $sc$ 单调递增，所以 s+sti≥fj2−fj1scj2−scj1s+st_i \\ge \\frac{f_{j_2}-f_{j_1}}{sc_{j_2}-sc_{j_1}}s+sti​≥scj2​​−scj1​​fj2​​−fj1​​​，即 ki≥Yj2−Yj1Xj2−Xj1k_i \\ge \\frac{Y_{j_2}-Y_{j_1}}{X_{j_2}-X_{j_1}}ki​≥Xj2​​−Xj1​​Yj2​​−Yj1​​​。

不等式右侧是 P(j2)P(j_2)P(j2​) 和 P(j1)P(j_1)P(j1​) 两点的斜率。即决策点 j2j_2j2​ 优于 j1j_1j1​ 满足的条件。

设有 $A,B,C$ 三点，满足 xa<xb<xcx_a < x_b < x_cxa​<xb​<xc​，且 k1=k(A,B),k2=k(B,C)k_1 = k(A, B),k_2 = k(B, C)k1​=k(A,B),k2​=k(B,C)。

如果 $k1>k2$，可以证明，$B$ 无论如何不会成为最优决策点，所以可以从候选决策点中删除。

所以，可以维护一个斜率递增下凸壳。

因为 $x$ 是随 $j$ 递增，所以下凸壳可以用单调队列维护。因为 kik_iki​ 随 $i$ 递增，所以具有决策单调性，及时将队首不够优秀的决策点出队。

时间复杂度为 $O(n)$

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 3e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-10;
typedef pair<int, int> pii;#define x(a) (c[a])
#define y(a) (f[a])
#define k(a) (t[a]+s)
ll t[maxn], c[maxn], f[maxn];
ll q[maxn], hh = 1, tt = 0;
long double slope(int a, int b){long double x1 = (long double)x(a);long double y1 = (long double)y(a);long double x2 = (long double)x(b);long double y2 = (long double)y(b);if(fabs(x2-x1) < eps)return y2 > y1 ? INF : -INF;elsereturn (y2-y1)/(x2-x1);
}
int n, s;
void init(){cin >> n >> s;int x, y;for(int i = 1; i <= n; i++){cin >> x >> y;t[i] = t[i-1] + x;c[i] = c[i-1] + y;}
}
void dp(){q[++tt] = 0;for(int i = 1; i <= n; i++){while(hh < tt && slope(q[hh], q[hh+1]) <= k(i)) hh++;int p = q[hh];f[i] = f[p] + (c[i]-c[p]) * t[i] + (c[n]-c[p]) * s;while(hh < tt && slope(q[tt-1], q[tt]) >= slope(q[tt], i)) tt--;q[++tt] = i;}cout << f[n] << endl;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> s;int x, y;for(int i = 1; i <= n; i++){cin >> t[i] >> c[i];t[i] += t[i-1];c[i] += c[i-1];}dp();return 0;
}

任务安排3

题意：

完全同上题。

数据规模：1≤n≤3×105,0≤s,ci≤512,−512≤ti≤5121 \\le n \\le 3\\times 10^5, 0 \\le s, c_i \\le 512, -512 \\le t_i \\le 5121≤n≤3×105,0≤s,ci​≤512,−512≤ti​≤512

解析：

y=fjy = f_jy=fj​，x=scjx = sc_jx=scj​，k=s+stik = s+st_ik=s+sti​，b=fi−(sti×sci+s×scn)b = f_i-(st_i\\times sc_i+s\\times sc_n)b=fi​−(sti​×sci​+s×scn​)

横坐标单调，斜率不单调。仍然可以用队列维护凸包，但最优决策点不知道在哪，不具有决策单调性，即不能让队首出队。寻找最优决策点时，在凸包上二分。

二分：在凸包上找到最优决策点 $j$，满足 k(j−1,j)≤ki<k(j,j+1)k(j-1, j) \\le k_i < k(j, j+1)k(j−1,j)≤ki​<k(j,j+1)

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 3e5+10;
const int maxm = 1e5+10;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;#define x(a) (c[a])
#define y(a) (f[a]) 
#define k(a) (t[a] + s)
using namespace std;
typedef long long LL;
const int N = 300005;
ll t[maxn], c[maxn], f[maxn];
ll q[maxn], hh = 1, tt = 0;
int n, s;long double slope(int a, int b){long double x1 = (long double)x(a);long double y1 = (long double)y(a);long double x2 = (long double)x(b);long double y2 = (long double)y(b);if(fabs(x2-x1) < eps)return y2 > y1 ? INF : -INF;elsereturn (y2-y1)/(x2-x1);
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> s;int x, y;for(int i = 1; i <= n; i++){cin >> t[i] >> c[i];t[i] += t[i-1];c[i] += c[i-1];}q[++tt] = 0;for (int i = 1; i <= n; i++) {int l = hh, r = tt;while(l < r) {int mid = (l+r) >> 1;if(slope(q[mid], q[mid+1]) >= k(i)) r = mid;else l = mid + 1;}int p = q[r];f[i] = f[p] + (c[i] - c[p]) * t[i] + (c[n] - c[p])* s;while(hh < tt && slope(q[tt-1], q[tt]) >= slope(q[tt], i)) tt--;q[++tt] = i;}cout << f[n] << endl;return 0;
}

运输小猫

题意：

$m$ 只猫，$p$ 个饲养员，$n$ 座山。第 $i-1$ 座山与第 $i$ 座山的距离为 did_idi​。第 $i$ 只猫在 hih_ihi​ 山上玩，在 tit_iti​ 时间开始等饲养员。饲养员从第 1 座山出发走到第 $n$ 座山，接正在等待的猫。使猫等待时间和最小。

解析：

对每只猫，求出饲养员出发的时间 aia_iai​，恰好使这只猫不用等待。ai=ti−∑k=1idka_i = t_i-\\sum\\limits_{k=1}\\limits^id_kai​=ti​−k=1∑i​dk​。

则如果饲养员在时刻 $t$ 出发，接上猫 $i$，猫 $i$ 的等待时间为 t−ait-a_it−ai​。

按 $a$ 排序。饲养员带走的一定是连续的猫。

令 fi,jf_{i,j}fi,j​ 为前 $i$ 个饲养员，带走前 $j$ 只猫 的最小等待时间和。

饲养员 $i$ 的出发时间一定为 aja_jaj​。如果 t<ajt < a_jt<aj​，接不到猫；如果 t>ajt > a_jt>aj​，可以更早出发使等待时间变短。

fi,j=min⁡{fi−1,k+∑u=k+1j(aj−au)}f_{i,j} = \\min\\Big\\{f_{i-1, k} + \\sum\\limits_{u=k+1}\\limits^j(a_j-a_u) \\Big\\}fi,j​=min{fi−1,k​+u=k+1∑j​(aj​−au​)}

前缀和优化：fi,j=min⁡{fi−1,k+aj×(j−k)−(sj−sk)}f_{i,j} = \\min\\Big\\{f_{i-1, k} + a_j\\times (j-k)-(s_j-s_k) \\Big\\}fi,j​=min{fi−1,k​+aj​×(j−k)−(sj​−sk​)} （$s$ 是 $a$ 的前缀和）

整理一下方程：fi−1,k+sk=aj×k+fi,j−aj×jf_{i-1, k}+s_k = a_j\\times k + f_{i,j} - a_j\\times jfi−1,k​+sk​=aj​×k+fi,j​−aj​×j

Y=fi−1,k+skY= f_{i-1, k}+s_kY=fi−1,k​+sk​，$X=k$，K=ajK = a_jK=aj​，B=fi,j−aj×jB = f_{i,j} - a_j\\times jB=fi,j​−aj​×j。

因为按 $a$ 升序排序，所以斜率单调。横坐标也单调。所以单调队列维护下凸壳，具有决策单调性。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const double eps = 1e-10;
const ll INF = 0x3f3f3f3f3f3f3f3f;ll f[110][maxn], s[maxn], a[maxn], d[maxn], g[maxn];
ll q[maxn], hh, tt;
int n, m, p;
long double slope(int a, int b){long double x1 = (long double)a;long double y1 = (long double)g[a];long double x2 = (long double)b;long double y2 = (long double)g[b];if(fabs(x2-x1) < eps)return y2 > y1 ? INF : -INF;elsereturn (y2-y1)/(x2-x1);
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m >> p;for(int i = 2, x; i <= n; i++){cin >> x;d[i] = d[i-1] + x;} for(int i = 1, x, k; i <= m; i++){cin >> x >> k;a[i] = k-d[x];}sort(a+1, a+1+m);for(int i = 1; i <= m; i++)s[i] = s[i-1] + a[i];memset(f, 0x3f,sizeof(f));f[0][0] = 0;for(int i = 1; i <= p; i++){for(int j = 1; j <= m; j++)g[j] = f[i-1][j]+s[j];q[1] = 0; hh = tt = 1;for(int j = 1; j <= m; j++){while(hh < tt && slope(q[hh], q[hh+1]) <= a[j]) hh++;f[i][j] = min(f[i-1][j], g[q[hh]]+a[j]*(j-q[hh])-s[j]);if(g[j] >= INF) continue;while(hh < tt && slope(q[tt-1], q[tt]) >= slope(q[tt], j)) tt--;q[++tt] = j;}}cout << f[p][m] << endl;return 0;
}