斜率优化dp 笔记

任务安排1

有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 00 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。

另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 Ci。

请为机器规划一个分组方案，使得总费用最小。

输入格式

第一行包含整数 N。

第二行包含整数 S。

接下来 N行每行有一对整数，分别为 Ti 和 Ci，表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。

输出格式

输出一个整数，表示最小总费用。

数据范围

1≤N≤5000,
0≤S≤50,
1≤Ti,Ci≤100

输入样例：

输出样例：

f[i]表示选好前i个任务的最小值

关键点在于把每次开始的S时间造成的全部后续影响加到当前这次的操作中，这样就不用考虑之前启动了几次机器了，取消了后效性

虽然过程中的f[1~n-1]的设计的值与状态设计不一定相同但f[n]一定是相同的

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 5010;int n, S;
ll T[N], C[N], sum[N];
ll f[N];int main()
{IOScin >> n >> S;for(int i = 1; i <= n; i ++)cin >> T[i] >> C[i];for(int i = 1; i <= n; i ++){sum[i] = sum[i - 1] + C[i];T[i] += T[i - 1];}for(int i = 1; i <= n; i ++){f[i] = 2e18;for(int j = 1; j <= i; j ++)//[j, i]{//关键点在于把每次开始的S时间造成的全部后续影响加到当前这次的操作中//虽然过程中的f[1~n-1]的设计的值与状态设计不一定相同但f[n]一定是相同的 ll res = f[j - 1] + T[i] * (sum[i] - sum[j - 1]) + S * (sum[n] - sum[j - 1]);f[i] = min(f[i], res);}}cout << f[n];return 0;
}

任务安排2

有 N个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。

另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 Ci。

请为机器规划一个分组方案，使得总费用最小。

输入格式

第一行包含整数 N。

第二行包含整数 S。

接下来 N 行每行有一对整数，分别为 Ti 和 Ci，表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。

输出格式

输出一个整数，表示最小总费用。

数据范围

1≤N≤3×1e5,
1≤Ti,Ci≤512,
0≤S≤512

输入样例：

输出样例：

除了数据范围其余和上一题一样

把j - 1看为 j可推出的公式： $f[i]=f[j]+T[i]*(C[i]-C[j])+S*(C[n]-C[j])$

可以发现当i固定时f[i]、C[i]、T[i]为定值，有两个未知量C[j]和f[j]

设f[j]为y,C[j]为x,整理一下式子

$f[j]=(T[i] + S) * C[j] + f[i] - T[i]*C[i] - S*C[n]$

约等于y = kx + b

可以发现截距b越小f[i]就越小，此时便来到了真正的斜率优化

找到下面最外围的凸包，找到第一个斜率大于k的那条边的左端点，此点就是在k斜率下到达y轴时最低的那个点（因为k>0° && k < 90°）

找这个凸包的办法：取出后两个点(x1,y1),(x2,y2)与当前点(x3,y3)比，如果第一个点和第二个点的斜率大于第一个点和第三个点的斜率就删掉最后一个点。循环往复。最后再加进这个点。

一般来说是用二分去找的

但这题还有点小性质，就是斜率k在不断变大，因此可以用类似双指针+单调队列的方式解决该问题（只是和单调队列很像）

任务安排3

有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。

另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 Ci。

请为机器规划一个分组方案，使得总费用最小。

输入格式

第一行包含两个整数 N 和 S。

接下来 N 行每行有一对整数，分别为 Ti 和 Ci，表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。

输出格式

输出一个整数，表示最小总费用。

数据范围

1≤N≤3×105,
0≤S,Ci≤512,
−512≤Ti≤512

输入样例：

输出样例：

这道题只能用二分了

过程会爆ll记得开int128

还有注意同一条线上的多个点只能存在最边缘的两个，中间的要全删掉

举个例子

1、2两点都符合要求，但1更好，可能会错求成2

1、2两点都行，但要选1而不能选2

但我写的二分会找到最左边的点，所以不是这里的问题，思来想去与第二题还有一点不同，就是S和T下限从1变成了0，就会出现横坐标不变的情况，出现了斜率无限大的情况，所以出现了=的情况

类似的情况会出现，造成难以估量的bug，所以，凸包一定不要留线段中间的点！！！

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 300010;int n, S;
ll T[N], C[N];
ll f[N];
int q[N];int main()
{IOScin >> n >> S;for(int i = 1; i <= n; i ++)cin >> T[i] >> C[i];for(int i = 1; i <= n; i ++){C[i] += C[i - 1];T[i] += T[i - 1];}int hh = 0, tt = -1;q[++ tt] = 0;for(int i = 1; i <= n; i ++){int l = hh, r = tt;while(l < r){int mid = l + r >> 1;ll x1 = C[q[mid]], y1 = f[q[mid]];ll x2 = C[q[mid + 1]], y2 = f[q[mid + 1]];if(y2 - y1 >= (T[i] + S) * (x2 - x1))r = mid;else l = mid + 1;} int j = q[l];f[i] = f[j] + T[i] * (C[i] - C[j]) + S * (C[n] - C[j]);ll x3 = C[i], y3 = f[i];while(hh < tt){ll x1 = C[q[tt - 1]], y1 = f[q[tt - 1]];ll x2 = C[q[tt]], y2 = f[q[tt]];//注意一定是>= !!!!!!if((__int128)(y2 - y1) * (x3 - x1) >= (__int128)(y3 - y1) * (x2 - x1))tt --;else break;}q[++ tt] = i;}cout << f[n];return 0;
}

运输小猫

小 S 是农场主，他养了 M 只猫，雇了 P 位饲养员。

农场中有一条笔直的路，路边有 N 座山，从 1 到 N 编号。

第 i 座山与第 i−1 座山之间的距离为 Di。

饲养员都住在 1 号山。

有一天，猫出去玩。

第 i 只猫去 Hi 号山玩，玩到时刻 Ti 停止，然后在原地等饲养员来接。

饲养员们必须回收所有的猫。

每个饲养员沿着路从 1 号山走到 N 号山，把各座山上已经在等待的猫全部接走。

饲养员在路上行走需要时间，速度为 1 米/单位时间。

饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。

例如有两座相距为 1 的山，一只猫在 2 号山玩，玩到时刻 3 开始等待。

如果饲养员从 1 号山在时刻 2 或 3 出发，那么他可以接到猫，猫的等待时间为 0 或 1。

而如果他于时刻 1 出发，那么他将于时刻 2 经过 2 号山，不能接到当时仍在玩的猫。

你的任务是规划每个饲养员从 1 号山出发的时间，使得所有猫等待时间的总和尽量小。

饲养员出发的时间可以为负。

输入格式

第一行包含三个整数 N，M，P。

第二行包含 n−1 个整数，D2,D3,…,DN。

接下来 M 行，每行包含两个整数 Hi 和 Ti。

输出格式

输出一个整数，表示所有猫等待时间的总和的最小值。

数据范围

2≤N≤1e5,
1≤M≤1e5,
1≤P≤100,
1≤Di<1000,
1≤Hi≤N,
0≤Ti≤1e9

输入样例：

输出样例：

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 110, M = 100010;int n, m, p;
ll f[N][M];//前i个人，收回前j只猫
ll d[M], a[M];
int q[M];
ll sum[M];ll gety(int i, int k)
{return f[i - 1][k] + sum[k];
}int main()
{IOScin >> n >> m >> p;for(int i = 2; i <= n; i ++){cin >> d[i];d[i] += d[i - 1];}for(int i = 1; i <= m; i ++){int h, t;cin >> h >> t;a[i] = t - d[h];}sort(a + 1, a + 1 + m);for(int i = 1; i <= m; i ++)sum[i] = sum[i - 1] + a[i];memset(f, 0x3f, sizeof f);//排除i个人带回0只小猫的代价为0for(int i = 0; i <= p; i ++)f[i][0] = 0;//派出0个人只有可能带回0只小猫 即f[0][0] = 0;已被包含for(int i = 1; i <= p; i ++){int hh = 0, tt = -1;q[++ tt] = 0;for(int j = 1; j <= m; j ++){//先把斜率小于a[j]的去掉while(hh < tt && gety(i, q[hh + 1]) - gety(i, q[hh]) < a[j] * (q[hh + 1] - q[hh]))hh ++;int k = q[hh];f[i][j] = f[i - 1][k] - sum[j] + sum[k] + j * a[j] - k * a[j];ll x3 = j, y3 = gety(i, j);while(hh < tt){ll x1 = q[tt - 1], y1 = gety(i, q[tt - 1]);ll x2 = q[tt], y2 = gety(i, q[tt]);if((y2 - y1) * (x3 - x1) >= (y3 - y1) * (x2 - x1))tt --;else break;}q[++ tt] = j;}}cout << f[p][m];return 0;
}