P2365 任务安排

洛谷数据较弱，LOJ有加强版

前缀和+斜率优化dp好题

题解：

考虑最朴素的$O(n^3)$dp

记t[i]表示各任务时间的前缀和，c[i]为各任务花费的前缀和

设f[i][j]表示前i个任务，分j批，且i是第j批的最后一个的最小花费

得到方程

尝试优化dp

注意到j这一维作用并不是很大，只是为了消除后效性，因为后面的任务不知道自己被分在第几批，前面有过几次S

考虑改用费用提前计算来消除后效性使得状态只需i一维

改设f[i]表示前i个任务造成的最小代价，且i是新分出一批的最后一个

我们知道分出i这一批会新产生两部分代价，一部分是这新一批内部产生的$t[i]*(c[i]-c[j])$，另一部分是这一批开机的S对后面所有任务产生的影响

加起来就可以得到一个新的二维dp方程

这已经可以使你通过洛谷上$O(n^2)$的数据了，但其实还可以继续优化

我们考虑斜率优化

先拆掉min并对上方的二维方程进行整理，得到$f[i]=f[j]-(S+t[i])c[j]+t[i]c[i]+S*c[n]$

常规操作，假设现有两个决策点j和k，且k优于j，将两者代入可以得到

继续整理：

发现左边的是个斜率，右边的满足单调性

所以就可以把这些东西用单调队列大胆维护了

再用每次的队首当作j来转移

dp被优化到了$O(n)$

注意比较斜率的一个常规操作，将除法交换成乘法以避免精度误差

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define qn (q.size()-1)

const int N=3e5+5;
int n,s,t[N],c[N],f[N];
deque<int> q;

signed main(){
    read(n);read(s);
    for(int i=1,x,y;i<=n;i++){
        read(x);read(y);
        t[i]=t[i-1]+x;
        c[i]=c[i-1]+y;
    }
    q.push_back(0);
    for(int i=1;i<=n;i++){
        while(q.size()>1&&(c[q[1]]-c[q[0]])*(t[i]+s)>=(f[q[1]]-f[q[0]])) q.pop_front(); //不满足了就踢掉
        f[i]=f[q[0]]-(s+t[i])*c[q[0]]+t[i]*c[i]+s*c[n]; //转移
        while(q.size()>1&&(f[i]-f[q[qn]])*(c[q[qn]]-c[q[qn-1]])<=(f[q[qn]]-f[q[qn-1]])*(c[i]-c[q[qn]])) q.pop_back(); //维护最优
        q.push_back(i);
    }
    write(f[n]);
}
赏

fighter