300 任务安排1（动态规划）

╰+攻爆jí腚メ 2022-09-15 05:47 150阅读 0赞

**1. 问题描述：**

有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。从时刻 0 开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 Ci。请为机器规划一个分组方案，使得总费用最小。

**输入格式**

第一行包含整数 N。第二行包含整数 S。接下来 N 行每行有一对整数，分别为 Ti 和 Ci，表示第 i 个任务单独完成所需的时间 Ti 及其费用系数 Ci。

**输出格式**

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

**数据范围**

1 ≤ N ≤ 5000，  
0 ≤ S ≤ 50，  
1 ≤ Ti，Ci ≤ 100

**输入样例：**

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

**输出样例：**

153  
来源：[https://www.acwing.com/problem/content/description/302/][https_www.acwing.com_problem_content_description_302]

**2. 思路分析：**

分析题目可以知道这道题目属于最优化问题，所以我们可以考虑使用**动态规划**的思想来解决。动态规划主要有两个步骤：① 状态表示；② 状态计算；因为是序列型的dp，所以我们声明一个一维数组dp，其中dp\[i\]表示将前i个任务处理完的所有方案的集合的最小值；因为这道题目中有一个启动时间的影响，由题目可知当前时刻的启动时间对于当前位置之后的所有位置都是有影响的，相当于我们需要在这个位置后面的所有位置对应的任务花费都需要累加上S，这里有一个比较巧妙的点是我们可以将所有由启动时间S影响的前缀和先处理出来，后面对于任务的开始位置只需要累加上由S影响的当前位置到最后一个位置的花费即可，根据下图的状态计算的分析可以知道可以先预处理一下Ci和Ti的前缀和，预处理好之后直接使用下图中的公式计算即可。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_18_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

if __name__ == "__main__":
        n = int(input())
        S = int(input())
        # 预处理前缀和
        sumt, sumc = [0], [0]
        for i in range(1, n + 1):
            t, c = map(int, input().split())
            sumt.append(sumt[i - 1] + t)
            sumc.append(sumc[i - 1] + c)
        f = [10 ** 15] * (n + 1)
        f[0] = 0
        for i in range(1, n + 1):
            for j in range(i):
                f[i] = min(f[i], f[j] + sumt[i] * (sumc[i] - sumc[j]) + S * (sumc[n] - sumc[j]))
        print(f[n])

[https_www.acwing.com_problem_content_description_302]: https://www.acwing.com/problem/content/description/302/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e484786ffb4d46b9a5aa6b2c1d9a575f.png