$任务安排$任务安排

机器上有N个需要处理的任务，它们构成了一个序列。这些任务被标号为1到N，因此序列的排列为1,2,3…N。这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和。注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。

$N\le 10^5,S\le 50-2^8\le T_i\le 2^8,0\le F_i\le 2^8$N≤105,S≤50−28≤Ti​≤28,0≤Fi​≤28

$最初想法$最初想法

$设$设

• $su{m}_t\left[i\right]$sumt​[i] 为前 $i$i 个任务的时间前缀和,
• $su{m}_c\left[i\right]$sumc​[i] 为前 $i$i 个任务的花费前缀和,
• $F[i,j]$F[i,j] 表示前 $i$i 个任务, 分成 $j$j 组的最小花费,

$则$则

$F[i,j]=\underset{}{\min }\left\{F\right[k,j-1]+(su{m}_t\left[i\right]+j\ast S)\ast (su{m}_c\left[i\right]-su{m}_c\left[k\right]\left)\right\}$F[i,j]=k∈[1,i)min​{F[k,j−1]+(sumt​[i]+j∗S)∗(sumc​[i]−sumc​[k])}

时间复杂度 $O\left(N^3\right)$O(N3).

$正解部分$正解部分

$设$设

• $F\left[i\right]$F[i] 表示前 $i$i 个任务的最小花费.

$F\left[i\right]=\underset{}{\min }\left\{F\right[j]+su{m}_t[i]\ast (su{m}_c\left[i\right]-su{m}_c\left[j\right])+S\ast \left(su{m}_c\right[N]-su{m}_c[j\left]\right)\}$F[i]=j∈[1,i)min​{F[j]+sumt​[i]∗(sumc​[i]−sumc​[j])+S∗(sumc​[N]−sumc​[j])}

这样转移可以以 $O\left(N^2\right)$O(N2) 的复杂度得出答案,
付出的代价仅为 “无法知道 $[1,N)$[1,N)内的花费”, 这样的代价对当前求解的问题并不会造成影响 .

但是 $O\left(N^2\right)$O(N2) 仍然不能过, 这时就需要 斜率优化 了, 没学过的可以看

这里 .

将式子中的 $\min$min 去掉, 移项为 $y=kx+b$y=kx+b 的形式 $\downarrow$↓ (为了方便将 $sum$sum 写成 $s$s)
$F\left[j\right]=s_c\left[j\right]\ast (S+s_t[i\left]\right)+F\left[i\right]-s_t\left[i\right]s_c\left[i\right]-S\ast s_c\left[N\right]$F[j]=sc​[j]∗(S+st​[i])+F[i]−st​[i]sc​[i]−S∗sc​[N]

• $y=F\left[j\right]$y=F[j]
• $x=s_c\left[j\right]$x=sc​[j]
• $k=S+s_t\left[i\right]$k=S+st​[i]
• $b=F\left[i\right]-s_t\left[i\right]s_c\left[i\right]-S\ast s_c\left[N\right]$b=F[i]−st​[i]sc​[i]−S∗sc​[N]

因为求的是 $\min$min, 所以使用单调队列维护 下凸壳, 单调队列内的斜率递增 .
由于 $k$k 不单调, 需要在单调队列中二分查找第一个斜率比 $k$k 大或等于的直线, 其左端点即为最优决策点

$实现部分$实现部分

注意斜率优化时二分出来的是队列中的下标, 而不是队列中的元素,
这道题卡精度, 正解卡成 $15$15 分 .

被卡代码 $\downarrow$↓

#include<bits/stdc++.h>
#define reg register
typedef long long ll;
 
const int maxn = 400005;
 
int N;
int S;
int T[maxn];
int C[maxn];
int Q[maxn];
 
ll F[maxn];
ll sumt[maxn];
ll sumc[maxn];
 
double X(int i){ return sumc[i]; }
 
double Y(int i){ return F[i]; }
 
double slope(int i, int j){ return ( Y(i)-Y(j) ) / ( X(i)-X(j) ); }
 
int main(){
        scanf("%d%d", &N, &S);
        for(reg int i = 1; i <= N; i ++){
                scanf("%d%d", &T[i], &C[i]);
                sumt[i] = sumt[i-1] + T[i];
                sumc[i] = sumc[i-1] + C[i];
        }
        int hd = 0, tl = 0; // hd = 1 !!
        for(reg int i = 1; i <= N; i ++){
                double k = S + sumt[i];
                int l = hd, r = tl;
                while(l < r){
                        int mid = l+r >> 1;
                        if(slope(Q[mid], Q[mid+1]) < k) l = mid + 1; // slope(mid, mid+1) !!
                        else r = mid;
                }
                int j = Q[r]; // !
                F[i] = F[j] + sumt[i]*(sumc[i]-sumc[j]) + S*(sumc[N]-sumc[j]);
                while(tl >= 1 && slope(Q[tl], Q[tl-1]) > slope(Q[tl], i)) tl --;
                Q[++ tl] = i;
                //printf("%d\n", tl);
        }
        printf("%lld\n", F[N]);
        return 0;
}

正确代码 $\downarrow$↓

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 400005;

int N;
int S;
int T[maxn];
int C[maxn];
int Q[maxn];

ll F[maxn];
ll sumt[maxn];
ll sumc[maxn];

double X(int i){ return sumc[i]; }

double Y(int i){ return F[i]; }

double slope(int i, int j){ return ( Y(i)-Y(j) ) / ( X(i)-X(j) ); }

int main(){
        scanf("%d%d", &N, &S);
        for(reg int i = 1; i <= N; i ++){
                scanf("%d%d", &T[i], &C[i]);
                sumt[i] = sumt[i-1] + T[i];
                sumc[i] = sumc[i-1] + C[i];
        }
        int hd = 0, tl = 0;
        for(reg int i = 1; i <= N; i ++){
                double k = S + sumt[i];
                int l = hd, r = tl;
                while(l < r){
                        int mid = l+r >> 1;
                        int a = Q[mid], b = Q[mid + 1];
                        if(Y(b)-Y(a) < k*(X(b)-X(a))) l = mid + 1;
                        else r = mid;
                }
                int j = Q[r]; // !
                F[i] = F[j] + sumt[i]*(sumc[i]-sumc[j]) + S*(sumc[N]-sumc[j]);
                while(tl >= 1){
                        int a = Q[tl], b = Q[tl-1], c = Q[tl], d = i;
                        if((Y(a)-Y(b))*(X(d)-X(c)) >= (Y(d)-Y(c))*(X(a)-X(b))) tl --; // >
                        else break ;
                }
                Q[++ tl] = i;
        }
        printf("%lld\n", F[N]);
        return 0;
}