当前位置：首页 > news >正文

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

news 来源：原创 2025/5/14 19:52:52

【题目链接】

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个子段的所有子段划分方案
条件：费用最小
统计量：费用

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

初始状态： $d p [i] [1]$ ：前i个元素分成1个子段的最小费用为 $(s+sumT[i])\cdot sumC[i]$ 。
结合后面的状态转移方程，该初始状态等价于先将dp数组设为无穷大，而后将 $d p [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任务耗费总时间为 $s u m T [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])$
因此状态转移方程为：
$min\{dp[k-1][j-1]+(s\cdot j+sumT[i])\cdot (sumC[i]-sumC[k])\}, j\le 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个子段“这一维度去掉。
$d p [i]$ 的意义为：前i个元素进行子段划分的所有方案中，费用最少的方案的费用。
如果这样进行状态定义，我们就无法得知前i个元素分成了几个子段，那么最后一个子段任务的完成时间 $s\cdot j+sumT[i]$ 中的子段数量j就是未知的。
这里可以将开机时间产生的费用和任务时间产生的费用分别考虑。
仍然设最后一个子段第一个元素的下标为k+1，那么 $0\le k < i$

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

如果完成时刻只考虑任务耗费时间，那么最后一个子段任务的完成时间为 $s u m T [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])$
我们把开机对后面所有任务产生的费用和完成任务的费用加在一起，作为状态定义。这是一种费用提前计算思想。
该方法最终的状态定义为：
$d p [i]$ ：前i个任务的所有子段划分方案中，执行任务的费用加上当前方案下每批任务的启动时间对后续任务产生的费用加和最小的划分方案的费用。
该状态定义与之前的状态定义（前i个元素进行子段划分的所有方案中，费用最少的方案的费用）不同，但该问题最终求的是 $d p [n]$ ，两种定义下 $d p [n]$ 的值一定是相同的。
根据上述分析，可知状态转移方程为：
$min\{dp[k]+sumT[i]\cdot (sumC[i]-sumC[k])+s\cdot (sumC[n]-sumC[k]), 0\le 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;
}

【题目链接】

【题目考点】

1. 动态规划：线性动规

【解题思路】

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

1. 确定状态：

2. 确定状态转移方程

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

【题解代码】

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

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

相关文章：

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

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

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

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