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

【题目链接】

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

【题目考点】

1. 动态规划：线性动规

【解题思路】

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

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

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

1. 确定状态：

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

状态定义$dp[i][j]$：前i个元素分成j个子段的所有子段划分方案中，费用最小的方案的费用。

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

2. 确定状态转移方程

策略集合：前i个元素分成j个子段的所有子段划分方案
分割策略集合：根据第j个子段的起始下标分割策略集合
设前j-1个子段包含序列下标1~k的元素。第j个子段的起始下标为k+1。
可知k的范围为$j<=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任务耗费总时间为$sumT[i]$，因此这批任务的完成时刻是$s\cdot j+sumT[i]$
第k+1个任务的费用为$(s\cdot j+sumT[i])\cdot c[k+1]$
第k+2个任务的费用为$(s\cdot j+sumT[i])\cdot c[k+2]$
…
第i个任务的费用为$(s\cdot j+sumT[i])\cdot c[i]$
因此总费用加和为$(s\cdot j+sumT[i])\cdot (sumC[i]-sumC[k])$
因此状态转移方程为：
d p [ i ] [ j ] = m i n { d p [ k − 1 ] [ j − 1 ] + ( s ⋅ j + s u m T [ i ] ) ⋅ ( s u m C [ i ] − s u m C [ k ] ) } , j ≤ k < i dp[i][j] = min\{dp[k-1][j-1]+(s\cdot j+sumT[i])\cdot (sumC[i]-sumC[k])\}, j\le k<i dp[i][j]=min{dp[k−1][j−1]+(s⋅j+sumT[i])⋅(sumC[i]−sumC[k])},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+sumT[i]$中的子段数量j就是未知的。
这里可以将开机时间产生的费用和任务时间产生的费用分别考虑。
仍然设最后一个子段第一个元素的下标为k+1，那么$0\le k<i$

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

如果完成时刻只考虑任务耗费时间，那么最后一个子段任务的完成时间为$sumT[i]$
最后一个子段的任务的费用分别是：
第k+1个任务的费用为$sumT[i]\cdot c[k+1]$
第k+2个任务的费用为$sumT[i]\cdot c[k+2]$
…
第i个任务的费用为$sumT[i]\cdot c[i]$
总费用为$sumT[i]\cdot (sumC[i]-sumC[k])$
然后考虑开机时间，当前最后一批任务（子段）的开机时间为s，由于这一次开机影响到的任务（元素）为第k+1任务到第n任务，这些任务的完成时间由于这一次开机延后了时间s，
产生的费用为$s\cdot c[k+1]+s\cdot c[k+2]+...+s\cdot c[n]$
$=s\cdot (sumC[n]-sumC[k])$
我们把开机对后面所有任务产生的费用和完成任务的费用加在一起，作为状态定义。这是一种费用提前计算思想。
该方法最终的状态定义为：
$dp[i]$：前i个任务的所有子段划分方案中，执行任务的费用 加上当前方案下每批任务的启动时间对后续任务产生的费用加和 最小的划分方案的费用。
该状态定义与之前的状态定义（前i个元素进行子段划分的所有方案中，费用最少的方案的费用）不同，但该问题最终求的是$dp[n]$，两种定义下$dp[n]$的值一定是相同的。
根据上述分析，可知状态转移方程为：
d p [ i ] = m i n { d p [ k ] + s u m T [ i ] ⋅ ( s u m C [ i ] − s u m C [ k ] ) + s ⋅ ( s u m C [ n ] − s u m C [ k ] ) , 0 ≤ k < i dp[i] = min\{dp[k]+sumT[i]\cdot (sumC[i]-sumC[k])+s\cdot (sumC[n]-sumC[k]), 0\le k< i dp[i]=min{dp[k]+sumT[i]⋅(sumC[i]−sumC[k])+s⋅(sumC[n]−sumC[k]),0≤k<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], st[N], sc[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];
 		st[i] = st[i-1]+t[i];
		sc[i] = sc[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+st[i])*(sc[i]-sc[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], sumT[N], sumC[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];
 		sumT[i] = sumT[i-1]+t[i];
		sumC[i] = sumC[i-1]+c[i];
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	for(int i = 1; i <= n; ++i)
		for(int k = 0; k <= i; ++k)
			dp[i] = min(dp[i], dp[k]+sumT[i]*(sumC[i]-sumC[k])+s*(sumC[n]-sumC[k]));
	cout << dp[n];
	return 0;
}