|
|
|
|
|
## [$AcWing$ $300$. 任务安排$1$](https://www.acwing.com/problem/content/302/)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
有 $N$ 个任务排成一个序列 **在一台机器上** 等待执行，它们的顺序不得改变。
|
|
|
|
|
|
|
|
|
|
|
|
机器会把这 $N$ 个任务分成若干批，每一批包含连续的若干个任务。
|
|
|
|
|
|
|
|
|
|
|
|
从时刻 $0$ 开始，任务被分批加工，执行第 $i$ 个任务所需的时间是 $T_i$。
|
|
|
|
|
|
|
|
|
|
|
|
另外，在每批任务开始前，机器需要 $S$ 的启动时间，故执行一批任务所需的时间是启动时间 $S$ 加上每个任务所需时间之和。
|
|
|
|
|
|
|
|
|
|
|
|
一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。
|
|
|
|
|
|
|
|
|
|
|
|
也就是说，**同一批任务将在同一时刻完成**。
|
|
|
|
|
|
|
|
|
|
|
|
每个任务的费用是 **它的完成时刻乘以一个费用系数 $C_i$**。
|
|
|
|
|
|
|
|
|
|
|
|
**请为机器规划一个分组方案，使得总费用最小**。
|
|
|
|
|
|
|
|
|
|
|
|
**输入格式**
|
|
|
|
|
|
第一行包含整数 $N$。
|
|
|
|
|
|
|
|
|
|
|
|
第二行包含整数 $S$。
|
|
|
|
|
|
|
|
|
|
|
|
接下来 $N$ 行每行有一对整数，分别为 $T_i$ 和 $C_i$，表示第 $i$ 个任务单独完成所需的时间 $T_i$ 及其费用系数 $C_i$。
|
|
|
|
|
|
|
|
|
|
|
|
**输出格式**
|
|
|
|
|
|
输出一个整数，表示最小总费用。
|
|
|
|
|
|
|
|
|
|
|
|
**数据范围**
|
|
|
|
|
|
$1≤N≤5000,0≤S≤50,1≤T_i,C_i≤100$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
5
|
|
|
|
|
|
1
|
|
|
|
|
|
1 3
|
|
|
|
|
|
3 2
|
|
|
|
|
|
4 3
|
|
|
|
|
|
2 3
|
|
|
|
|
|
1 4
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
**输出样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
153
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、理解用例
|
|
|
|
|
|
|
|
|
|
|
|
假如这样分组：
|
|
|
|
|
|
<center><img src='https://img2022.cnblogs.com/blog/8562/202202/8562-20220225080930242-1683909927.png'></center>
|
|
|
|
|
|
|
|
|
|
|
|
最佳答案是$153$，我们现在算出来是$163$，很显然这不是最优的办法。
|
|
|
|
|
|
|
|
|
|
|
|
最优的解是这样的：
|
|
|
|
|
|
<center><img src='https://img2022.cnblogs.com/blog/8562/202202/8562-20220228163353376-1223038245.png'></center>
|
|
|
|
|
|
|
|
|
|
|
|
### 二、暴力枚举$MLE$
|
|
|
|
|
|
|
|
|
|
|
|
空间复杂度$O(n^2)$、时间复杂度$O(n^3)$
|
|
|
|
|
|
|
|
|
|
|
|
<center><img src='https://img2022.cnblogs.com/blog/8562/202202/8562-20220225112415345-1173659176.png'></center>
|
|
|
|
|
|
|
|
|
|
|
|
**状态表示**：
|
|
|
|
|
|
- 集合:$f[i][j]$表示前$i$个任务分成$j$组的集合
|
|
|
|
|
|
- 属性:最小费用
|
|
|
|
|
|
|
|
|
|
|
|
**状态计算**：
|
|
|
|
|
|
$$\large f[i][j]=min(f[k][j−1]+(j×s+\sum_{a=1}^{i}t[i])×(\sum_{a=k+1}^ic[i])),k \in [j-1,i)$$
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
**最后一个不同点**：最后一组，枚举最后一组的起点：可以分为前$k$个机器分为$j−1$组，$k+1 \sim i$个机器是第$j$组
|
|
|
|
|
|
|
|
|
|
|
|
$\displaystyle \sum_{a=1}^i t[i]$和$\displaystyle \sum_{a=k+1}^{i}c[i]$可以用前缀和优化
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#### 暴力代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
|
|
|
const int N = 5010;
|
|
|
|
|
|
int t[N], c[N];
|
|
|
|
|
|
int f[N][N];
|
|
|
|
|
|
int n, s;
|
|
|
|
|
|
/**
|
|
|
|
|
|
5
|
|
|
|
|
|
1
|
|
|
|
|
|
1 3
|
|
|
|
|
|
3 2
|
|
|
|
|
|
4 3
|
|
|
|
|
|
2 3
|
|
|
|
|
|
1 4
|
|
|
|
|
|
|
|
|
|
|
|
答案：153
|
|
|
|
|
|
|
|
|
|
|
|
二维数组：
|
|
|
|
|
|
5000*5000=25000000
|
|
|
|
|
|
|
|
|
|
|
|
25000000 * 4byte=100000000 byte = 100000 kb = 100 mb >题目要求的64mb ，所以不出意外：
|
|
|
|
|
|
MLE了！还没有来的及TLE，先MLE了！看来需要一个一维的状态表示方法！
|
|
|
|
|
|
*/
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
// 任务个数与启动时间
|
|
|
|
|
|
cin >> n >> s;
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
|
|
|
cin >> t[i] >> c[i];
|
|
|
|
|
|
t[i] += t[i - 1]; // t数组自带前缀和
|
|
|
|
|
|
c[i] += c[i - 1]; // c数组自带前缀和
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
/* 1、为什么这样初始化？
|
|
|
|
|
|
答：看状态转移方程
|
|
|
|
|
|
f[i][j] = min(f[i][j], f[k][j - 1] + (j * s + t[i]) * (c[i] - c[k]));
|
|
|
|
|
|
f[i][j]：前i个任务，在j个阶段的场景下，最小的代价值是多少。
|
|
|
|
|
|
|
|
|
|
|
|
这个k好说，有上面的循环限制了它的范围。
|
|
|
|
|
|
这个j-1就要小心了，不能小于零吧~，而且，如果等于0是啥意思，也要从现实意义出发进行初始化设置
|
|
|
|
|
|
j-1=0,也就是说在第0个阶段，第0个阶段就是还没有开始,管你前多少个任务，代价值都应该是0
|
|
|
|
|
|
*/
|
|
|
|
|
|
memset(f, 0x3f, sizeof f);
|
|
|
|
|
|
memset(f[0], 0, sizeof f[0]);
|
|
|
|
|
|
|
|
|
|
|
|
// 2、开始填表
|
|
|
|
|
|
for (int i = 1; i <= n; i++) // i个任务
|
|
|
|
|
|
for (int j = 1; j <= i; j++) // j个阶段，注意j的上界，一个阶段1个任务是极限，此时i=j
|
|
|
|
|
|
for (int k = j - 1; k < i; k++) // 最后一个阶段的起点k
|
|
|
|
|
|
f[i][j] = min(f[i][j], f[k][j - 1] + (s * j + t[i]) * (c[i] - c[k])); // 前缀和 \sum_{a=k+1}^{i}c[a]
|
|
|
|
|
|
|
|
|
|
|
|
/*
|
|
|
|
|
|
3、收集答案
|
|
|
|
|
|
f[n]表示在n个任务,那么划分的分组数量可能是多少呢？是1，2，3，...n,其中1表示全部划归一组,n表示一个任务一组，共n组
|
|
|
|
|
|
*/
|
|
|
|
|
|
int res = INF;
|
|
|
|
|
|
for (int i = 1; i <= n; i++) res = min(res, f[n][i]);
|
|
|
|
|
|
cout << res << endl;
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 四、优化：费用提前计算
|
|
|
|
|
|
|
|
|
|
|
|
#### 为什么要写暴力?
|
|
|
|
|
|
所有题目拿下来都可以先向暴力的方向去想，然后再进行优化
|
|
|
|
|
|
|
|
|
|
|
|
#### 进一步思考
|
|
|
|
|
|
我们为什么要枚举每一组？是为了得到启动机器的次数进而算费用
|
|
|
|
|
|
我们可以发现，只要我们分一组，后面还未分组的机器一定会增加相应的费用，高兴的是我们现在就可以算出来增加的费用是多少，所以我们只需要提前把这个多出来的费用加上就行了
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
**状态表示**：
|
|
|
|
|
|
- 集合:$f[i]$表示前$i$个任务处理完的所有方案的集合
|
|
|
|
|
|
> 不关心划分成多少个组
|
|
|
|
|
|
|
|
|
|
|
|
- 属性:最小费用
|
|
|
|
|
|
|
|
|
|
|
|
**考虑最后一个不同点**
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
假设当前正在思考$f[i]$,它前面的最后一个任务终点$j$在哪里,很明显，$j \in [0,i)$,$i$在最后一组中。
|
|
|
|
|
|
|
|
|
|
|
|
当在$j+1$处创建一个新的分组时，那么后续的所有任务，都将增加$S$的时间，总共的增加时长=$(c[n]-c[j])\times s$
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
**状态转移方程**：
|
|
|
|
|
|
$$\large f[i]=min(f[j]+(c[i]−c[j])×t[i]+(c[n]−c[j])×s), j \in [0,i)$$
|
|
|
|
|
|
|
|
|
|
|
|
同上$c[i]$和$t[i]$是前缀和。
|
|
|
|
|
|
|
|
|
|
|
|
### 四、$AC$代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
typedef long long LL;
|
|
|
|
|
|
const int N = 5010;
|
|
|
|
|
|
int n; // n个任务
|
|
|
|
|
|
LL s; // 等待时间
|
|
|
|
|
|
LL c[N]; // 每个任务都有一个花费， 用c[i]来表示,更新概念为前缀和
|
|
|
|
|
|
LL t[N]; // 每个任务都有一个执行时间,用t[i]来表示,更新概念为前缀和
|
|
|
|
|
|
LL f[N]; // 前i个任务，不管划分多少个阶段，最小代价是多少
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
cin >> n >> s;
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
|
|
|
cin >> t[i] >> c[i];
|
|
|
|
|
|
t[i] += t[i - 1];
|
|
|
|
|
|
c[i] += c[i - 1];
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
// 初始化
|
|
|
|
|
|
memset(f, 0x3f, sizeof f);
|
|
|
|
|
|
f[0] = 0;
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 1; i <= n; i++) // 从小到大枚举每个任务
|
|
|
|
|
|
for (int j = 0; j < i; j++) // j:前一个批次的最后一个位置
|
|
|
|
|
|
f[i] = min(f[i], f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]));
|
|
|
|
|
|
// 输出
|
|
|
|
|
|
cout << f[n] << endl;
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
