信息学奥赛一本通 1606：【 例 1】任务安排 1 | 洛谷 P2365 任务安排

【题目链接】

ybt 1606：【 例 1】任务安排 1
洛谷 P2365 任务安排

【题目考点】

1. 动态规划：线性动规

【解题思路】

可以先了解法1，虽然不是正解，但该解法只使用了动规的基本思路，易于理解，有助于理解这一问题。而后再了解该题的正解解法2。

解法1（非正解）： 二维状态，$O(n^3)$解法

第i个任务执行时间为$t_i$，第i个任务的费用系数为为$c_i$
记序列t的前缀和为T，序列c的前缀和为C
抽象问题，可知：每个任务是一个元素，构成一个序列。一批任务就是序列的一个子段。划分批次的方案，就是对一个序列划分为多个子段的方案。

1. 确定状态：

• 阶段：前i个元素，分成j个子段
• 决策：一个元素被分到哪一个子段
• 策略：子段划分方案
• 策略集合：前i个元素分成j个子段的所有子段划分方案
• 条件：费用最小
• 统计量：费用

状态定义$d{p}_{i,j}$：前i个元素分成j个子段的所有子段划分方案中，费用最小的方案的费用。

• 初始状态：$d{p}_{i,1}$：前i个元素分成1个子段的最小费用为$(s+T_i)\cdot C_i$。
  结合后面的状态转移方程，该初始状态等价于先将dp数组设为无穷大，而后将$d{p}_{0,0}$设为0

2. 确定状态转移方程

策略集合：前i个元素分成j个子段的所有子段划分方案
分割策略集合：根据第j个子段的起始下标分割策略集合
设前j-1个子段包含序列下标1~k的元素。第j个子段的起始下标为k+1。
可知k的范围为$j\le k<i$

当前面j-1个子段每个子段只有一个数字时，k最小，为j。
当第j个子段只有一个数字时，k最大，为i-1。

当第j子段的起始下标为k+1时，前k个数字分成j-1个子段的最小费用，再加上第j个子段的费用，就是当前子段划分下的最小费用。

第1到第i任务一共有j个子段（批次），开机启动耗时$s\cdot j$。第1个任务到第i任务耗费总时间为$T[i]$，因此这批任务的完成时刻是$s\cdot j+T_i$
第k+1个任务的费用为$(s\cdot j+T_i)\cdot c_{k+1}$
第k+2个任务的费用为$(s\cdot j+T_i)\cdot c_{k+2}$
…
第i个任务的费用为$(s\cdot j+T_i)\cdot c_i$
因此总费用加和为$(s\cdot j+T_i)\cdot (C_i-C_k)$
因此状态转移方程为：
d p i , j = m i n { d p k − 1 , j − 1 + ( s ⋅ j + T i ) ⋅ ( C i − C k ) } , j ≤ k < i dp_{i,j} = min\{dp_{k-1,j-1}+(s\cdot j+T_i)\cdot (C_i-C_k)\}, j\le k<i dpi,j​=min{dpk−1,j−1​+(s⋅j+Ti​)⋅(Ci​−Ck​)},j≤k<i

该解法的时间复杂度是$O(n^3)$。
在洛谷上是70分，一本通上是60分。
有测试点超时，因为n是5000，$O(n^3)$必然会超时。
有测试点是答案错误，因为结果会超过int的范围，需要使用long long类型表示。而如果开long long dp[5005][5005]，又会空间超限。所以开int dp[5005][5005]，有些测试点的结果由于超出int的范围而产生答案错误。

解法2（正解）： 一维状态，$O(n^2)$解法

上一解法在确定状态转移方程时是这样做的：
当第j子段的起始下标为k+1时，前k个数字分成j-1个子段的最小费用，再加上第j个子段的费用，就是当前子段划分下的最小费用。
第j个子段也就是前i个元素进行划分子段所得到的最后一个子段。最后一个子段确定后，第1~k元素自然需要选择费用最少的子段划分方案，无论分成多少子段。
因此我们可以把状态定义中”分成j个子段“这一维度去掉。
$dp[i]$的意义为：前i个元素进行子段划分的所有方案中，费用最少的方案的费用。
如果这样进行状态定义，我们就无法得知前i个元素分成了几个子段，那么最后一个子段任务的完成时间$s\cdot j+T_i$中的子段数量j就是未知的。
这里可以将开机时间产生的费用和任务时间产生的费用分别考虑。
仍然设最后一个子段第一个元素的下标为k+1，那么$0\le k<i$

当1~i整个序列就是最后一个子段，此时k最小为0
当最后一个子段只有一个第i元素，次数k最大为i-1

如果完成时刻只考虑任务耗费时间，那么最后一个子段任务的完成时间为$T[i]$
最后一个子段的任务的费用分别是：
第k+1个任务的费用为$T_i\cdot c_{k+1}$
第k+2个任务的费用为$T_i\cdot c_{k+2}$
…
第i个任务的费用为$T_i\cdot c_i$
总费用为$T_i\cdot (C_i-C_k)$
然后考虑开机时间，当前最后一批任务（子段）的开机时间为s，由于这一次开机影响到的任务（元素）为第k+1任务到第n任务，这些任务的完成时间由于这一次开机延后了时间s，
产生的费用为$s\cdot c_{k+1}+s\cdot c_{k+2}+...+s\cdot c_n$
$=s\cdot (C_n-C_k)$
我们把开机对后面所有任务产生的费用和完成任务的费用加在一起，作为状态定义。这是一种费用提前计算思想。
该方法最终的状态定义为：
$d{p}_i$：前i个任务的所有子段划分方案中，执行任务的费用 加上当前方案下每批任务的启动时间对后续任务产生的费用加和 最小的划分方案的费用。
该状态定义与之前的状态定义（前i个元素进行子段划分的所有方案中，费用最少的方案的费用）不同，但该问题最终求的是$d{p}_n$，两种定义下$d{p}_n$的值一定是相同的。
根据上述分析，可知状态转移方程为：
d p i = m i n { d p k + T i ⋅ ( C i − C k ) + s ⋅ ( C n − C k ) } , 0 ≤ k < i dp_i = min\{dp_k+T_i\cdot (C_i-C_k)+s\cdot (C_n-C_k)\}, 0\le k< i dpi​=min{dpk​+Ti​⋅(Ci​−Ck​)+s⋅(Cn​−Ck​)},0≤k<i
该解法下变量j没有用到，个人习惯能用j就不用k。可以将符号k替换为符号j，状态转移方程为：
d p i = m i n { d p j + T i ⋅ ( C i − C j ) + s ⋅ ( C n − C j ) } , 0 ≤ j < i dp_i = min\{dp_j+T_i\cdot (C_i-C_j)+s\cdot (C_n-C_j)\}, 0\le j< i dpi​=min{dpj​+Ti​⋅(Ci​−Cj​)+s⋅(Cn​−Cj​)},0≤j<i
该解法时间复杂度为$O(n^2)$，空间复杂度$O(n)$，可以通过此题。

【注】本题可以进一步通过斜率优化使得时间复杂度降至$O(n)$，该方法见[洛谷 P10979 任务安排 2]

【题解代码】

解法1（非正解）： 二维状态，$O(n^3)$解法 （洛谷70分 一本通60分）

#include<bits/stdc++.h>
using namespace std;
#define N 5005
int n, s, t[N], c[N], T[N], C[N], dp[N][N], ans = 1e9;//dp[i][j]：前i个数字分成j个子段的所有方案中，费用最小的方案的费用
int main()
{cin >> n >> s;for(int i = 1; i <= n; ++i){cin >> t[i] >> c[i];T[i] = T[i-1]+t[i];C[i] = C[i-1]+c[i];}memset(dp, 0x3f, sizeof(dp));dp[0][0] = 0;for(int i = 1; i <= n; ++i)for(int j = 1; j <= i; ++j)for(int k = j; k <= i; ++k)dp[i][j] = min(dp[i][j], dp[k-1][j-1]+(s*j+T[i])*(C[i]-C[k-1]));for(int j = 1; j <= n; ++j)ans = min(ans, dp[n][j]);cout << ans;return 0;
}

解法2（正解）： 一维状态，$O(n^2)$解法

#include<bits/stdc++.h>
using namespace std;
#define N 5005
long long n, s, t[N], c[N], T[N], C[N], ans = 1e18, dp[N];//dp[i]:前i个任务的所有子段划分方案中，执行任务的费用 加上当前方案下每批任务的启动时间对后续任务产生的费用加和 最小的划分方案的费用
int main()
{cin >> n >> s;for(int i = 1; i <= n; ++i){cin >> t[i] >> c[i];T[i] = T[i-1]+t[i];C[i] = C[i-1]+c[i];}memset(dp, 0x3f, sizeof(dp));dp[0] = 0;for(int i = 1; i <= n; ++i)for(int j = 0; j <= i; ++j)dp[i] = min(dp[i], dp[j]+T[i]*(C[i]-C[j])+s*(C[n]-C[j]));cout << dp[n];return 0;
}