Description
如前面提到，ABC的汽车工厂有N个工人，他们在一个传送带上生产汽车，工人从左到右排列，编号依次为1到N，采用流水线模式，每个人负责自己的一部分工作。
生产一台汽车需要从1号工人开始，当1号完成他的工作后，2号就会开始工作，然后是3号，最后当N号工人完成他的工作后，整个汽车生产完毕。工人们一共需要生产M台汽车，而且必须按照从1到M的顺序去生产。
对于工人i，他完成自己的工作需要Ti的时间，而对于汽车j，组装复杂度为Fj。那么工人i花在汽车j上的时间为Ti*Fj。
当某个工人完成他的工作后，他会同时把汽车交给下一个工人，没有任何时间上的延迟，因此，要保证下一个要接受汽车的工人必须是空闲的。为了满足这个要求，ABC需要为每一台汽车选择一个好时机开始制造。
ABC想知道生产完所有汽车最少需要多少时间。
Solution
设 \(g_i\) 表示第 \(i\) 辆汽车开始工作的时间，\(s_i\) 表示 \(t_i\) 的前缀和。
有转移方程 \(g_i=g_{i-1}+\max\{s_jf_{i-1}-s_{j-1}f_i\}\)。
可以暴力枚举 \(j\)，时间复杂度 \(\mathcal O(n^2)\)，期望得分 \(40\text{pts}\)。
考虑斜率优化，若 \(j\) 没有 \(k\) 优，则有 \(s_jf_{i-1}-s_{j-1}f_i<s_kf_{i-1}-s_{k-1}f_i\)，移项变形可得 \(\frac{f_i}{f_{i-1}}<\frac{s_k-s_j}{s_{k-1}-s_{j-1}}\)。
\(\frac{f_i}{f_{i-1}}\) 不单调，则维护斜率单调递减的上凸壳，然后二分。
Code
#include<cstdio>
#include<algorithm>
#define N 100005
#define ll long long
#define db double
using namespace std;
int n,m,t,l,r,mid,res,q[N];
ll a[N],b[N],f[N];
int read()
{
int res=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();
return res;
}
ll llread()
{
ll res=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();
return res;
}
db xl(int x,int y) {return (a[x]-a[y])/(db)(a[x-1]-a[y-1]);}
int main()
{
n=read();m=read();
for (int i=1;i<=n;++i)
a[i]=llread(),a[i]+=a[i-1];
for (int i=1;i<=m;++i)
b[i]=llread();
for (int i=1;i<=n;++i)
{
while (t>1&&xl(i,q[t])>xl(q[t],q[t-1])) --t;
q[++t]=i;
}
f[1]=0;
for (int i=2;i<=m;++i)
{
l=0;r=t;res=0;
db x=b[i]/(db)b[i-1];
while (l<r)
{
mid=(l+r)>>1;
if (xl(q[mid+1],q[mid])>x) l=mid+1;
else r=mid;
}
f[i]=f[i-1]+a[q[l]]*b[i-1]-a[q[l]-1]*b[i];
}
printf("%lld\n",f[m]+a[n]*b[m]);
return 0;
}
Thank
感谢 大佬的博客。