FJOI 日常原题 $2333$（似乎还不如 SDOI2012 任务安排 $2333$）
显然考虑 $dp$，这个是经典的把未来的代价先计算的 $dp$，然后才是斜率优化
一开始想状态时一直有一个时间维，然后就没法优化，考虑如何消掉这个时间维
可以发现，时间只和当前处理到的任务编号，和之前启动机器的次数（分的段数）有关
然后就可以设 $f[i][j]$ 表示前 $i$ 个任务，分了 $j$ 段，然后就可以 $O(n^3)$ $dp$ 了（然鹅此时并不能斜率优化...）
考虑怎么优化，发现每次分的时候都要产生 $s$ 的时间，而这 $s$ 的时间不仅仅是加在 $j$ 到 $i$ 这一段
它是加在 $j$ 到 $n$ 的，所以考虑把到 $n$ 的代价也计算进去（把这一段的代价先提前计算）
这样之后转移的时候就不用考虑因为分段而多出来的时间了
设 $st[i]$ 表示前 $i$ 个任务的完成时间和，$sc[i]$ 表示前 $i$ 个任务的费用和
设 $f[i]$ 表示完成前 $i$ 个任务分了若干段的最小代价，那么可以得出 $dp$ 方程：
$f[i]=sum_{j=1}^{i-1}min( f[j]+(sc[n]-sc[j])*S+st[i]*(sc[i]-sc[j]) )$
然后复杂度是 $n^2$...
发现好像可以斜率优化了，把式子拆开：
$f[i]=f[j]+sc[n]*S-sc[j]*S+st[i]*sc[i]-st[i]*sc[j]$
$f[i]=f[j]-(st[i]+S)sc[j]+sc[n]S+st[i]sc[i]$
$(st[i]+S)sc[j]+f[i]-st[i]sc[i]+sc[n]S=f[j]$
那么 $k=st[i]+S,x=sc[j],b=f[i]-st[i]sc[i]+sc[n]S,y=f[j]$
因为 $k,x$ 单调，所以直接斜率优化...（SDOI那题好像因为 $t[i]$ 可以小于 $0$ 所以要上 $CDQ$ ?）
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; typedef double db; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e6+7; int n,S; int st[N],sc[N]; ll f[N]; inline ll X(int i) { return sc[i]; } inline ll Y(int i) { return f[i]; } inline db slope(int i,int j) { return 1.0*(Y(i)-Y(j))/(X(i)-X(j)); } int Q[N],l=1,r=1; int main() { n=read(),S=read(); for(int i=1;i<=n;i++) st[i]=st[i-1]+read(),sc[i]=sc[i-1]+read(); for(int i=1;i<=n;i++) { while( l<r && 1.0*(st[i]+S)>=slope(Q[l],Q[l+1]) ) l++; int j=Q[l]; f[i]=f[j]+(sc[n]-sc[j])*S+st[i]*(sc[i]-sc[j]); while( l<r && slope(Q[r-1],i)<=slope(Q[r-1],Q[r]) ) r--; Q[++r]=i; } printf("%lld",f[n]); return 0; }