题解 P5785 【[SDOI2012]任务安排】

Stay_Hungry · 2020-01-14 11:42:29 · 题解

从0.1开始的斜率优化（dalao请跳过，不喜误喷）

因为我是真的菜，写不来逼格高的，只得写篇详细而通俗易懂的题解。

那么何为“斜率优化”呢？
答曰：用线性规划优化dp式。

如果不会线性规划，问题也不大，接下来开始题解正文部分：

以下正文部分分成3类数据题解。

其实我个人感觉O(n^3)dp很难想=-=

按照题意来，我们设f_i表示完成到以第i个任务为结束任务时所花费的最短时间

外层枚举i，内层枚举j，表示从j+1到i这一段任务加入到f_j所表示的任务安排区间，然后加上贡献取min即可。

对于开机时间，只会对开机一次后的任务产生影响，所以直接加上S*(c_{j+1}+...+c_{n})，对于这段任务的完成费用，直接前缀和T_i乘一下即可

所以我们可以得出dp式：

然后用前缀和维护c(a,b)，这样就愉快的切掉弱化版P2365。

分析复杂度：内外两层循环，时间复杂度为O(n^2)，是肯定不行的，然后此时我们就得用斜率优化来优化时间复杂度。

我们把Min去除，然后化简，用其他元素表示f_j

这样我们就可以得到一个一次函数解析式。

然而为啥要这么分呢？
答曰：把外循环时可以不能直接得出的放在x或y处，k和b都是可以依靠外指针i得到的，然后就可以开始愉快的斜率优化啦！

对于选择不同的j更新f_i的值，我们把j称为决策点，对于任意一个决策点，我们都能把它表示在以sc_j为x轴，以f_j为y轴的平面直角坐标系上。

对于一个决策点所对应的直线，都可以解出一段截距b，而

了解大致原理后，我们需先分析单调性。
当j单调递增时，c_i>0，因此sc_j单调递增，且t_i>0，因此f_i单调递增，k单调递增。

接下来我们就需考虑最优决策点的选择。
通俗一点讲，所谓选择最优决策点就是把一条斜率为s+sc_i的直线从下向上靠，第一个相交的点就是最优决策点（因为此时b最小，f_i也必定最小）。

而对于上凸点，无论直线的斜率怎么变化，最先相交的点必定不是上凸点，因此我们可以将所有上凸点都移出决策点队列，最后，我们可以得到一个下凸包。

因此对于任意决策点a,b,c (a<b<c)，满足k_a<k_b<k_c，即决策点斜率单调递增。
因为k单调递增，因此小于当前k(k=s+sc_i)决策点可以移出决策点队列。

分析时间复杂度：每个点进出队列1次，时间复杂度O(n)。

此时t_i可能为负数，因此f_j不一定单调递增，所以决策点连线的直线可能为负数，决策时k也可能为负数。

同样，上凸点一定不是最优决策点，因此需维护下凸包。

在此，此篇题解就告一段落了，献上代码：

#include <cstdio>
#include <iostream>
typedef long long ll;
const int N = 3e5 + 5 ;
int l = 1 , r = 0 ;
ll sc[N], st[N], f[N], n, s, q[N];
ll Y(int p) {return f[p];}
ll X(int p) {return sc[p];}
ll K(int p) {return s + st[p];}
int Search(int L, int R, long long S) {
    int M = 0 , Res = r ;
    while(L <= R) {
        M = ( L + R ) >> 1; 
        if(Y(q[M + 1]) - Y(q[M]) > S * (X(q[M + 1]) - X(q[M]))) // 由所得性质二分
            R = M - 1, Res = M;
        else L = M + 1; // 二分+-1防止死循环
    }
    return q[Res];
} // 二分查找决策点
int main() {
    scanf("%lld %lld", &n, &s);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld %lld", st + i, sc + i);
        st[i] += st[i - 1];
        sc[i] += sc[i - 1];
    } // 前缀和
    q[++ r] = 0 ;// 0 为第一个决策点
    for(int i = 1; i <= n; ++i) {
        int p = Search(l, r, K(i));
        f[i] = f[p] + s * (sc[n] - sc[p]) + st[i] * (sc[i] - sc[p]); // 按照dp方程式更新答案
        while(l < r && (Y(q[r]) - Y(q[r - 1])) * (X(i) - X(q[r])) 
            >= (Y(i) - Y(q[r])) * (X(q[r]) - X(q[r - 1]))) -- r; // 除去上凸点 ， 这里把算斜率的除法转换为乘法以防误差
        q[++ r] = i; // 入队列
    }
    printf("%lld\n", f[n]); // 完美输出
    return 0; // 好习惯
}

updated on 12-15：毒瘤码风修复，最初方程得出过程已添加