思路：题面真心长....单调栈维护上凸壳即可
设sum[i]为前i道工序的复杂度之和，g[i]为第i个快乐最早开始生产的时间。因为我们要保证没有两个快乐同时出现在同一道工序，所以
g[i]=g[i-1]+max(sum[j]*f[i-1]-sum[j-1]*f[i])
然后就是像斜率优化的过程了
sum[j]*f[i-1]=f[i]*sum[j-1]+g[i]-g[i-1]
sum[j]=f[i]/f[i-1]*sum[j-1]+(g[i]-g[i-1])/f[i-1]
y = k * x + b
于是可以发现使g[i]最大的点一定在一个上凸壳上，因为查询的斜率f[i]/f[i-1]不单调，用单调栈维护，二分查询即可。
#include#include #include #include #define max(a,b) (a>b?a:b)#define ll long longconst int maxn=2000010,inf=(int)1e9;const double eps=1e-9;using namespace std;int n,m,sum[maxn],f[maxn],t[maxn],q[maxn],top;ll tim,g[maxn];char ch;void read(int &x){ for (ch=getchar();!isdigit(ch);ch=getchar()); for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';} double slope(int i,int j){ if (i==0||j==0) return inf; if (i==inf||j==inf) return -inf; return 1.0*(sum[i]-sum[j])/(double)(sum[i-1]-sum[j-1]);} void work(){ q[1]=0,q[2]=1,top=2,q[top+1]=inf,g[1]=0; for (int i=2;i<=n;i++){ for (;top&&slope(i,q[top])>slope(q[top],q[top-1])+eps;) { top--; } q[++top]=i,q[top+1]=inf; } for (int i=2;i<=m;i++){ int l=1,r=top,mid=(l+r)>>1;double k=(1.0*f[i])/(1.0*f[i-1]); while (1){ if (slope(q[mid],q[mid-1])+eps>=k&&slope(q[mid],q[mid+1])<=k+eps) break; else if (slope(q[mid],q[mid+1])>k+eps) l=mid+1; else r=mid-1; mid=(l+r)>>1; } g[i]=g[i-1]+(ll)sum[q[mid]]*f[i-1]-(ll)sum[q[mid]-1]*f[i]; } printf("%lld\n",1ll*(g[m]+1ll*sum[n]*f[m]));} int main(){ freopen("yume.in","r",stdin);freopen("yume.out","w",stdout); read(n),read(m); for (int i=1;i<=n;i++) read(t[i]),sum[i]=sum[i-1]+t[i]; for (int i=1;i<=m;i++) read(f[i]); work(); fclose(stdout); return 0;}