洛谷P2365/5785 任务安排 题解 斜率优化DP资料

本文主要介绍洛谷P2365/5785 任务安排 题解 斜率优化DP资料 方法和在新技术下所面对的“挑战”,方便大家深入理解洛谷P2365/5785 任务安排 题解 斜率优化DP资料 过程。本文也将分享洛谷P2365/5785 任务安排 题解 斜率优化DP资料 所遇到的问题和应对策略,怎么解决怎么做的问题。
通过深入本文可以理解代码原理,进行代码文档的下载,也可以查看相应 Demo 部署效果。

任务安排1(小数据):https://www.luogu.com.cn/problem/P2365
任务安排2(大数据):https://www.luogu.com.cn/problem/P5785

题目描述

(N) 个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。机器会把这 (N) 个任务分成若干批,每一批包含连续的若干个任务。从时刻 (0) 开始,任务被分批加工,执行第 (i) 个任务所需的时间是 (T_i)。另外,在每批任务开始前,机器需要 (S) 的启动时间,故执行一批任务所需的时间是启动时间 (S) 加上每个任务所需时间之和。

一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。也就是说,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 (C_i)

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

输入格式

第一行是 (N) ,第二行是 (S)

下面 (N) 行每行有一对数,分别为 (T_i)(C_i),均为不大于 (100) 的正整数,表示第 (i) 个任务单独完成所需的时间是 (T_i) 机器费用系数 (C_i)

输出格式

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

样例输入

5 1 1 3 3 2 4 3 2 3 1 4 

样例输出

153 

数据规模

50%的数据保证 (1 lt N le 5000, 1 le S le 50, 1 le T_i, C_i le 100)
100%的数据保证 (1 le N le 3 times 10^5, 1 le S,T_i,C_i le 512)

问题分析

解法一:

求出 (T,C) 的前缀和 (sumT,sumC),即

[sumT[i] = sum_{j=1}^{i} T_j ]

[sumC[i] = sum_{j=1}^{i} C_j ]

(F[i][j]) 表示把前 (i) 个任务分成 (j) 批执行的最小费用,则第 (j) 批任务的完成时间就是 (j times S + sumT[i])

以第 (j-1) 批和第 (j) 批任务的分界点为DP的“决策”,(设第 (j-1) 批的最后一个任务是 (k),第 (j) 批的最后一个任务是 (i))状态转移方程为:

[F[i][j] = min_{0 le k lt i} { F[k][j-1] + (S times j + sumT[i]) times (sumC[i] – sumC[k]) } ]

实现代码如下:

#include <bits/stdc++.h> using namespace std; const int maxn = 5000; int n, S, T, C, sumT[maxn], sumC[maxn], f[maxn][maxn], ans = -1; int main() {     cin >> n >> S;     for (int i = 1; i <= n; i ++) {         cin >> T >> C;         sumT[i] = sumT[i-1] + T;         sumC[i] = sumC[i-1] + C;     }     memset(f, -1, sizeof(f));     for (int j = 1; j <= n; j ++) {         for (int i = j; i <= n; i ++) {             if (j == 1) {                 f[i][j] = (S + sumT[i]) * sumC[i];                 continue;             }             for (int k = j-1; k < i; k ++) {                 assert(f[k][j-1] != -1);                 int tmp = f[k][j-1] + (S * j + sumT[i]) * (sumC[i] - sumC[k]);                 if (f[i][j] == -1 || f[i][j] > tmp) f[i][j] = tmp;             }         }     }     for (int i = 1; i <= n; i ++) {         if (ans == -1 || ans > f[n][i]) ans = f[n][i];     }     cout << ans << endl;     return 0; } 

该解法的时间复杂度是 (O(n^3))

解法二:

本题并没有规定需要把任务分成多少批,在上一个解法中之所以需要批数 (j),是因为我们需要知道机器启动了多少次(每次启动都要 (S) 单位时间),从而计算出 (i) 所在的一批任务的完成时刻。

事实上,在执行一批任务时,我们不容易直接得知在此之前机器启动过几次。但我们知道,机器因执行这批任务而花费的启动时间 (S),会累加到在此之后所有任务的完成时刻上。

(F[i]) 表示把前 (i) 个任务分成若干批执行的最小费用,状态转移方程为:

[F[i] = min { F[j] + sumT[i] times (sumC[i] – sumC[j]) + S times (sumC[N] – sumC[j]) } ]

在上式中,第 (j+1 sim i) 个任务在同一批内完成,(sumT[i]) 是忽略机器的启动时间,这批任务的完成时刻。因为这批任务的执行,机器的启动时间 (S) 会对第 (j+1) 个之后的所有任务产生影响,故我们把这部分补充到费用中。

也就是说,我们没有直接求出每批任务的完成时间,而是在一批任务“开始”对后续任务产生影响时,就先把费用累加到结果中。这是一种名为 “费用提前计算” 的经典思想。

实现代码如下:

#include <bits/stdc++.h> using namespace std; const int maxn = 5000; int n, S, T, C, sumT[maxn], sumC[maxn], f[maxn]; int main() {     cin >> n >> S;     for (int i = 1; i <= n; i ++) {         cin >> T >> C;         sumT[i] = sumT[i-1] + T;         sumC[i] = sumC[i-1] + C;     }     memset(f, -1, sizeof(f));     f[0] = 0;     for (int i = 1; i <= n; i ++) {         for (int j = 0; j < i; j ++) {             int tmp = f[j] + sumT[i] * (sumC[i] - sumC[j]) + S * (sumC[n] - sumC[j]);             if (f[i] == -1 || f[i] > tmp) f[i] = tmp;         }     }     cout << f[n] << endl;     return 0; } 

该解法的时间复杂度为 (O(N^2))

解法三:

对上一题的算法二进行优化,先对状态转移方程稍作变形,把常数、仅与 (i) 有关的项、仅与 (j) 有关的项 以及 (i,j) 的乘积项分开。

[F[i] = min_{0 le j lt i} { F[j] – (S + sumT[i]) times sumC[j] } + sumT[i] times sumC[i] + S times sumC[N] ]

(min) 函数去掉,把关于 (j) 的值 (F[j])(sumC[j]) 看做变量,其余部分看做常数,得到:

[F[j] = (S + sumT[i]) times sumC[j] + F[i] – sumT[i] times sumC[i] – S times sumC[N] ]

(sumC[j]) 为横坐标, (F[j]) 为纵坐标的平面直角坐标系中,这是一条以 (S + sumT[i]) 为斜率,(F[i] – sumT[i] times sumC[i] – S times sumC[N]) 为截距的直线。也就是说,决策候选集合是坐标系中的一个点集,每个决策 (j) 都对应着坐标系中的一个点 ((sumC[j], F[j]))。每个待求解的状态 (F[i]) 都对应着一条直线的截距,直线的斜率是一个固定的值 (S + sumT[i]),截距未知。当截距最小化时,(F[i]) 也取到最小值。

该问题实际上是一个线性规划问题,高中数学有所涉及。令直线过每个决策点 ((sumC[j], F[j])),都可以求得一个截距,其中使截距最小的一个就是最优决策。体现在坐标系中,就是用一条斜率为固定正整数的直线自下而上平移,第一次接触到某个决策点时,就得到了最小截距。如图所示:

洛谷P2365/5785 任务安排 题解 斜率优化DP

对于任意三个决策点 ((sumC[j_1], F[j_1]))((sumC[j_2], F[j_2]))((sumC[j_3], F[j_3])),不妨设 (j_1 lt j_2 lt j_3),因为 (T,C) 均为正整数,亦有 (sumC[j_1] lt sumC[j_2] lt sumC[j_3])。根据及时排除无用决策的思想,我们考虑 (j_2) 可能成为最优决策的条件。

洛谷P2365/5785 任务安排 题解 斜率优化DP

从上图中我们发现,(j_2) 有可能成为最优决策,当且仅当 (j_1)(j_2) 的斜率小于 (j_2)(j_3) 的斜率,即:

[frac{F[j_2] – F[j_1]}{sumC[j_2] – sumC[j_1]} lt frac{F[j_3] – F[j_2]}{sumC[j_3] – sumC[j_2]} ]

小于号两侧实际上都是连接两个决策点的线段的斜率。通俗地讲,我们应该维护“连接相邻两点的线段斜率”单调递增的一个“下凸壳”,只有这个“下凸壳”的顶点才有可能成为最优决策。实际上,对于一条斜率为 (k) 的直线,若某个顶点左侧线段线段的斜率比 (k) 小,右侧线段的斜率比 (k) 大,则该顶点就是最优决策。换言之,如果把这条直线和所有线段组成一个序列,那么令直线截距最小化的顶点就出现在按照斜率大小排序时,直线应该排在的位置上。如图所示:

洛谷P2365/5785 任务安排 题解 斜率优化DP

在本题中,(j) 的取值范围是 (0 le j lt i),随着 (i) 的增大,每次会有一个新的决策进入候选集合。因为 (sumC) 的单调性,新决策在坐标系中的横坐标一定大于之前的所有决策,出现在凸壳的最右端。另外,因为 (sumT) 的单调性,每次求解“最小截距”的直线斜率 (S+sumT[i]) 也单调递增,如果我们只保留凸壳上“连接相邻两点的线段斜率”大于 (S+sumT[i]) 的部分,那么凸壳的最左端点就一定是最优决策。

综上所述,我们可以建立单调队列 (q),维护这个下凸壳。队列中保存若干个决策变量,它们对应凸壳上的顶点,且满足横坐标 (sumC) 递增、连接相邻两点的线段斜率也递增。需要支持的操作与一般的单调队列题目类似,对于每个状态变量 (i)

  1. 检查队首的两个决策变量 (Q_l)(Q_{l+1}),若斜率 (frac{F[Q_{l+1}] – F[Q_l]}{sumC[Q_{l+1}] – sumC[Q_l]} le S + sumT[i]),则让 (Q_l) 出队,继续检查新的队首。
  2. 直接取队首 (j = Q_l) 为最优决策,执行状态转移,计算出 (F[i])
  3. 把新决策 (i) 从队尾插入,在插入之前,若三个决策点 (j_1 = Q_{r-1}, j_2 = Q_r, j_3 = i) 不满足斜率单调递增(不满足下凸性,即 (j_2) 是无用决策),则直接从队尾让 (Q_r) 出队,继续检查新的队尾。

实现代码如下:

#include <bits/stdc++.h> using namespace std; const int maxn = 300030; int n, q[maxn], l, r; long long S, T, C, sumT[maxn], sumC[maxn], f[maxn]; int main() {     cin >> n >> S;     for (int i = 1; i <= n; i ++) {         cin >> T >> C;         sumT[i] = sumT[i-1] + T;         sumC[i] = sumC[i-1] + C;     }     memset(f, -1, sizeof(f));     f[0] = 0;     q[l = r = 1] = 0;     for (int i = 1; i <= n; i ++) {         while (l < r && f[q[l+1]] - f[q[l]] <= (S + sumT[i]) * (sumC[q[l+1]] - sumC[q[l]])) l ++;         f[i] = f[q[l]] - (S + sumT[i]) * sumC[q[l]] + sumT[i] * sumC[i] + S * sumC[n];         while (l < r && (f[q[r]]-f[q[r-1]]) * (sumC[i]-sumC[q[r]]) >= (f[i]-f[q[r]]) * (sumC[q[r]]-sumC[q[r-1]])) r --;         q[++r] = i;     }     cout << f[n] << endl;     return 0; } 

整个算法的时间复杂度为 (O(N))

与一般的单调队列优化DP的模型相比,本题维护的“单调性”依赖于队列中相邻两个元素之间的某种“比值”。因为这个值对应线性规划的坐标系中的斜率,所以我们在本题中使用的优化方法称为“斜率优化”。


以上分析针对 (T_i) 为正数的情况,接下来我们来考虑 (T_i) 为负数的情况。


与任务安排1不同的是,任务安排2中任务的执行时间 (T) 可能是负数。这意味着 (sumT) 不具有单调性,从而需要最小化截距的直线的斜率 (S + sumT[i]) 不具有单调性。所以,我们不能在单调队列中只保留凸壳上“连接相邻两点的线段斜率”大于 (S + sumT[i]) 的部分,而是必须维护整个凸壳。这样一来,我们就不需要在队首把斜率与 (S + sumT[i]) 比较。

队首也不一定是最优决策,我们可以在单调队列中二分查找,求出一个位置 (p)(p) 左侧线段的斜率比 (S + sumT[i]) 小,右侧线段的斜率比 (S+sumT[i]) 大,(p) 就是最优决策。

实现代码如下:

#include <bits/stdc++.h> using namespace std; const int maxn = 300030; int n, q[maxn], l, r; long long S, T, C, sumT[maxn], sumC[maxn], f[maxn]; int my_binary_search(int k) {     if (l == r) return q[l];     int L = l, R = r;     while (L < R) {         int mid = (L + R) / 2;         if (f[q[mid+1]] - f[q[mid]] <= k * (sumC[q[mid+1]] - sumC[q[mid]])) L = mid + 1;         else R = mid;     }     return q[L]; } int main() {     cin >> n >> S;     for (int i = 1; i <= n; i ++) {         cin >> T >> C;         sumT[i] = sumT[i-1] + T;         sumC[i] = sumC[i-1] + C;     }     memset(f, -1, sizeof(f));     f[0] = 0;     q[l = r = 1] = 0;     for (int i = 1; i <= n; i ++) {         int p = my_binary_search(S + sumT[i]);         f[i] = f[p] - (S + sumT[i]) * sumC[p] + sumT[i] * sumC[i] + S * sumC[n];         while (l < r && (f[q[r]]-f[q[r-1]]) * (sumC[i]-sumC[q[r]]) >= (f[i]-f[q[r]]) * (sumC[q[r]]-sumC[q[r-1]])) r --;         q[++r] = i;     }     cout << f[n] << endl;     return 0; } 

洛谷P2365/5785 任务安排 题解 斜率优化DP资料部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 洛谷P2365/5785 任务安排 题解 斜率优化DP资料

提供最优质的资源集合

立即查看 了解详情