题解：P10979 任务安排 2

__Inv_day_in_R__ · 2024-11-21 21:03:38 · 题解

本题是 P2365 的强化版，先思考 P2365 怎么做。

我们用 dp_i 来表示 i+1 重新启动机器，区间 1 到 i 之间费用的最小值。不难想到每次机器启动都会给之后的所有机器都带来 s 的时间，则启动代价为 s\sum\limits_{k=i+1}^{n}C_k，设上一次由 dp_j 转移来，j+1 到 i 之间运行代价为 \sum\limits_{k=j+1}^iC_k\sum\limits_{k=1}^iT_k。

这里使用前缀和优化，最终，得到如下的转移方程：

时间复杂度 O(n^2)，可以通过 P2365。

接下来考虑本题的斜率优化。斜率优化需要对原方程进行变形，先省略 \min，相当于求 dp_i=dp_j+(C_i-C_j)T_i+(C_n-C_j)s 的最小值。 接下来如下进行变形：

化成这个形式之后，发现像一个一次函数，于是以 C_j 为 x 轴，dp_j 为 y 轴建立平面直角坐标系，平面上第 j 个点为 (C_j,dp_j)，而每次转移时的 T_i+s 与 -C_iT_i-C_ns 都是一个常量，要使 dp_i 最小也就是在前 i-1 个点中选出过这个点，斜率为定值的直线中截距最小的那个。

不难发现，答案必然在原点集的一个右下凸包上：

考虑如何动态维护凸包。C_i 单调递增，所以新加入的点必然在右边。

如上图，CD 斜率大于 DE 斜率，所以 D 被删除，然后再看 BC 与 CE。

查询时二分即可。 代码如下：

#include<iostream>
#define int long long 
using namespace std;
int n,s,t[300010],c[300010],f[300010];
int q[300010];
main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>c[i];
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }
    int hh=0,tt=0;
    q[0]=0;
    for(int i=1;i<=n;i++){
        int l=hh,r=tt;
        while(l<r){
            int mid=l+r>>1;
            if((__int128)(t[i]+s)*(c[q[mid+1]]-c[q[mid]])<(__int128)(f[q[mid+1]]-f[q[mid]]))r=mid;
            else l=mid+1;
        }
        int j=q[r];
        f[i]=f[j]+c[i]*t[i]-c[j]*t[i]+c[n]*s-c[j]*s;
        while(hh<tt&&(__int128)(f[i]-f[q[tt]])*(c[q[tt]]-c[q[tt-1]])<=(__int128)(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]]))tt--;
        q[++tt]=i;
    }
    cout<<f[n];
}

这个代码还能过 P5785。