来自 这篇笔记 第3部分。

由于AcWing的LaTeX有点奇怪，所以文中所有应该用 {} 表示的minmax全部采用小括号

题目链接

LOJ10184
AcWing300
P2365
任务安排1

LOJ10185
AcWing301
任务安排2

LOJ10186
AcWing302
P5785
任务安排3

注：此处范围、AC代码均以 AcWing 为准。

题意

有 $N$ 个任务等待完成（顺序不改变），这 $N$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $Ti$ 。只有一台机器，在每批任务开始前，机器需要启动时间 $S$，完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以它的费用系数 $Ci$。请确定一个分组方案，使得总费用最小。

T1

$1⩽N⩽5000,0⩽S⩽50,1⩽T_i,C_i⩽100$

令 $sumT[i]=\sum_{j=1}^i T[j],sumC[i]=\sum_{j=1}^i F[j]$，那么
$$ f[p][i]=min( f[p-1][j]+(sumT[i]+p\times S)\times (sumC[i]-sumC[j]) ) $$
考虑费用提前计算。每次分出一批任务，对后面的每个任务的用时都会产生 $S$ 的贡献，那么可以提前计算。
$$ f[i]=min(f[j]+sumT[i]\times ( sumC[i]-sumC[j] )+S\times (sumC[n]-sumC[j]) ) $$

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int n,s,t[N],c[N],f[N];

int main() 
{
    scanf( "%d%d",&n,&s );
    for ( int i=1; i<=n; i++ )
        scanf( "%d%d",t+i,c+i );

    memset( f,0x3f,sizeof f );
    f[0]=0;
    for ( int i=1; i<=n; i++ )
        t[i]+=t[i-1],c[i]+=c[i-1];
    for ( int i=1; i<=n; i++ )
     for ( int j=0; j<i; j++ )
        f[i]=min( f[i],f[j]+(c[i]-c[j])*t[i]+s*(c[n]-c[j]) );

    printf( "%d\n",f[n] );
} 

T2

$1\leq N\leq 3e5$ $1\leq T_i,C_i\leq 512,0\leq S\leq 512$

$N$ 变大了，需要加上斜率优化。
$$ f[i]=min(f[j]+sumT[i]\times (sumC[i]-sumC[j])+S\times (sumC[n]-sumC[j]) ) $$
考虑转化成斜率式子。
$$ f[j]=(sumT[i]+S)\times sumC[j] + f[i]-sumC[i]\times sumT[i]-sumC[n]\times S $$

代码

#include <bits/stdc++.h>
#define ll long long
#define lb long double
using namespace std;
const int N=3e5+10;
int n,s,q[N],h=0,t=0;
ll sc[N],st[N],f[N];

lb slope( int x,int y ) { return (lb)(f[y]-f[x])/(sc[y]-sc[x]); }

int main()
{
    scanf( "%d%d",&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];
    }

    for ( int i=1; i<=n; i++ )
    {
        while ( h<t && slope(q[h],q[h+1])<=( st[i]+s ) ) h++;
        f[i]=f[q[h]]-( st[i]+s )*sc[q[h]]+sc[i]*st[i]+s*sc[n];
        while ( h<t && slope(q[t-1],q[t])>=slope(q[t],i) ) t--;
        q[++t]=i;
    }

    printf( "%lld",f[n] );
}

T3

$1\leq N\leq 3e5,0\leq S,C_i\leq 512,|T_i|\leq 512$

任务的执行时间 $t$ 可能是负数，那么斜率不具有单调性，
就不能只保留大于 $S+sumT[i]$ 的部分，而应该维护整个凸壳
此时队头不一定是最优决策，需要进行二分查找，求出一个位置，
使左侧的斜率小于 $S+sumT[i]$ ，右侧斜率大于 $S+sumT[i]$

注：此题 AcWing 上数据较强，建议把 slope 改为交叉相乘，需要使用 __int128 或者 double .

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+10;
int n,s,q[N],h=0,t=0;
ll sc[N],st[N];
double f[N];

int main()
{
    scanf( "%d%d",&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];
    }

    for ( int i=1; i<=n; i++ )
    {
        int l=h,r=t;
        while ( l<r )
        {
            int mid=(l+r)/2;
            if ( (f[q[mid+1]]-f[q[mid]])>(st[i]+s)*(sc[q[mid+1]]-sc[q[mid]]) ) r=mid;
            else l=mid+1;
        }
        f[i]=f[q[l]]-( st[i]+s )*sc[q[l]]+sc[i]*st[i]+s*sc[n];
        while ( h<t && ( f[q[t]]-f[q[t-1]] )*( sc[i]-sc[q[t]] )>=( f[i]-f[q[t]] )*( sc[q[t]]-sc[q[t-1]]  ) ) t--;
        q[++t]=i;
    }

    printf( "%.0lf",f[n] );
}