由于这三道题都是同一道题,只是数据范围不同,故拉成同一篇博客
题意
有$n$个任务,机器人($jxc$)会把这$n$个任务分成若干批,从时刻$0$开始,任务将被分批加工,执行第$i$个任务需要花费时间为$T_i$。另外,在每一批任务开始前,机器需要$S$的启动时间。
同一批任务将在同一时刻完成。每个任务的费用$=$它完成的时间$\times$一个费用的系数$C_i$。
思路
对于$n \leq 5000$的数据
时间复杂度$O(N^2)$
设$f[i]$表示前$i$个任务所花费最小价值。
初始化:
$$f[i]=inf|1<=i<=n,f[0]=0$$
转移方程:
$$f[i]=min \left{f[j-1]+S(c[n]-c[j-1])+t[i](c[i]-c[j-1])|1<=j<=i \right}$$
1 | #include<bits/stdc++.h> |
对于$1\leq N \leq 10^4$的数据
时间复杂度约为$O(N)$
转移方程同上,
$$f[i]=min \left{ f[j-1]+S(c[n]-c[j-1])+t[i](c[i]-c[j-1])|1<=j<=i \right }$$
将只含有$i$的项移出,得:
$$f[i]=min \left { f[j-1]-Sc[j-1]-t[i]c[j-1]|1<=j<=i \right }+Sc[n]+t[i]c[i]$$
合并同类项,得:
$$f[i]=min \left { f[j]-(S+t[i])c[j]|0<=j<=i-1 \right }+Sc[n]+t[i]*c[i]$$
设$y=f[j]$,$k=S+t[i]$,$x=c[j]$,$b=Sc[n]+t[i]c[i]$
那么:
$$f[i]=y-kx+b$$
即:
$$y=kx+(f[i]-b)$$
斜率优化一:
因为$t[i]$在递增,斜率$k$在变大,直线越来越陡,所以队首的两个点之间斜率至少要大于$(S+t[i])$。
即:$(f[q[l+1]]-f[q[l]])/(c[q[l+1]]-c[q[l]])>(S+t[i])$
即:若$(f[q[l+1]]-f[q[l]])/(c[q[l+1]]-c[q[l]])<=(S+t[i])$,队首弹出
化简,得:若$(f[q[l+1]]-f[q[l]])<=(S+t[i])*(c[q[l+1]]-c[q[l]])$,队首弹出斜率优化二:
确保右侧的斜率大于左侧的斜率,即:$(f[q[r]]-f[q[r-1]])/(c[q[r]]-c[q[r-1]])<(f[i]-f[q[r]])/(c[i]-c[q[r]])$。
若$(f[q[r]]-f[q[r-1]])/(c[q[r]]-c[q[r-1]])>=(f[i]-f[q[r]])/(c[i]-c[q[r]])$,队尾弹出。
化简,得:若$(f[i]-f[q[r]])(c[q[r]]-c[q[r-1]])<=(f[q[r]]-f[q[r-1]])(c[i]-c[q[r]])$,队尾弹出
1 | #include<bits/stdc++.h> |
对于$1 \leq N \leq 3 \times 10^5 , \left| T_i \right|<2^8$的数据
虽然添加了单调队列的优化,但是时间可以为负数,所以之前维护的单调性就不存在了,所以我们需要使用二分+单调队列来维护斜率。
1 | #include<bits/stdc++.h> |