BZOJ2726 [SDOI2012]任务安排 [斜率优化动态规划]

$任务安排$

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

$Nle10^5, Sle50\-2^8le T_i le 2^8, 0le F_i le 2^8$

---

$color{blue}{最初想法}$

$设$

• $sum_t[i]$ 为前 $i$ 个任务的时间前缀和,
• $sum_c[i]$ 为前 $i$ 个任务的花费前缀和,
• $F[i,j]$ 表示前 $i$ 个任务, 分成 $j$ 组的最小花费,

$则$

$F[i,j]=minlimits_{k∈[1,i)} { F[k,j-1]+(sum_t[i]+j*S)*(sum_c[i]-sum_c[k])}$

时间复杂度 $O(N^3)$.

---

$color{red}{正解部分}$

$设$

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

$F[i]=minlimits_{j∈[1,i)}{F[j]+sum_t[i]*(sum_c[i]-sum_c[j])+color{red}{S*(sum_c[N]-sum_c[j])}}$

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

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

这里 .

将式子中的 $min$ 去掉, 移项为 $y=kx+b$ 的形式 $↓$ (为了方便将 $sum$ 写成 $s$)
$F[j] = s_c[j]*(S+s_t[i])+F[i]-s_t[i]s_c[i]-S*s_c[N]$

• $y = F[j]$
• $x = s_c[j]$
• $k = S+s_t[i]$
• $b = F[i]-s_t[i]s_c[i]-S*s_c[N]$

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

---

$color{red}{实现部分}$

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

被卡代码 $↓$

#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
", tl);
        }
        printf("%lld
", F[N]);
        return 0;
}

正确代码 $↓$

#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
", F[N]);
        return 0;
}