洛谷傳送門

FJOI 日常原題 $2333$（似乎還不如 SDOI2012 任務(wù)安排 $2333$）

顯然考慮 $dp$，這個是經(jīng)典的把未來的代價先計算的 $dp$，然后才是斜率優(yōu)化

一開始想狀態(tài)時一直有一個時間維，然后就沒法優(yōu)化，考慮如何消掉這個時間維

可以發(fā)現(xiàn)，時間只和當前處理到的任務(wù)編號，和之前啟動機器的次數(shù)（分的段數(shù)）有關(guān)

然后就可以設(shè) $f[i][j]$ 表示前 $i$ 個任務(wù)，分了 $j$ 段，然后就可以 $O(n^3)$ $dp$ 了（然鵝此時并不能斜率優(yōu)化...）

考慮怎么優(yōu)化，發(fā)現(xiàn)每次分的時候都要產(chǎn)生 $s$ 的時間，而這 $s$ 的時間不僅僅是加在 $j$ 到 $i$ 這一段

它是加在 $j$ 到 $n$ 的，所以考慮把到 $n$ 的代價也計算進去（把這一段的代價先提前計算）

這樣之后轉(zhuǎn)移的時候就不用考慮因為分段而多出來的時間了

設(shè) $st[i]$ 表示前 $i$ 個任務(wù)的完成時間和，$sc[i]$ 表示前 $i$ 個任務(wù)的費用和

設(shè) $f[i]$ 表示完成前 $i$ 個任務(wù)分了若干段的最小代價，那么可以得出 $dp$ 方程：

$f[i]=\sum_{j=1}^{i-1}min(\ f[j]+(sc[n]-sc[j])*S+st[i]*(sc[i]-sc[j])\ )$

然后復(fù)雜度是 $n^2$...

發(fā)現(xiàn)好像可以斜率優(yōu)化了，把式子拆開：

$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$ 單調(diào)，所以直接斜率優(yōu)化...（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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LLTYYC/p/10743196.html

總結(jié)

以上是生活随笔為你收集整理的luogu P2365 任务安排（FJOI2019 batch）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。