P5785 [SDOI2012]任务安排
分析
很明显是一个dp
我们不妨设\(dp[i]\)表示枚举到\(i\)的最小费用
\(t[i]\)表示加工完第\(i\)个任务所用的总时间，也就是\(T[i]\)的前缀和
由于每一批任务前都要一个时间为\(s\)的开机工作
我们不妨把每一个这样的\(s\)秒提出来，则这\(s\)秒都会对后面所有的\(c[i]\)产生影响
\(dp[i]= \min(dp[j]+s * \sum_{k=j+1}^{k \le n}{c[k]}+t[i] * \sum_{k=j+1}^{k \le i}{c[k]})\)
我们再用\(sumc[i]\)表示\(c\)数组的前缀和
那么
\(dp[i]=\min(dp[j]+s * (sumc[n]-sumc[j])+t[i] * (sumc[i]-sumc[j]) )\)
设\(F[i]=s * (sumc[n]-sumc[i])\),\(G[i]=t[i]* sumc[i]\)
则\(dp[i]=\min(dp[j]+F[j]+G[i]-t[i]* sumc[j])\)
\(dp[i]=\min(dp[j]+F[j]-t[i]* sumc[j])+G[i]\)
这就是一个可以用斜率优化的dp方程式了
斜率优化
- 设两个决策点\(j_1,j_2(j_2>j_1)\)，\(j_2\)优于\(j_1\)
注意此时\(sumc[j_2]>sumc[j_1]\)，那么在后续的化简中，遇到负数要变号
\(dp[j_1]+F[j_1]-t[i]* sumc[j_1] \ge dp[j_2]+F[j_2]-t[i]* sumc[j_2]\) - 拆开不等式
\((dp[j_1]+F[j_1])-(dp[j_2]+F[j_2) \ge t[i]* (sumc[j_1]-sumc[j_2])\)
注意这里的\(sumc[j_1]-sumc[j_2] \lt 0\)，所以下一步需要变号
\(\frac{(dp[j_1]+F[j_1])-(dp[j_2]+F[j_2])}{sumc[j_1]-sumc[j_2]} \le t[i]\)
\(\frac{(dp[j_2]+F[j_2])-(dp[j_1]+F[j_1])}{sumc[j_2]-sumc[j_1]} \le t[i]\)
还可以再把\(F[i]\)代入进行化简
\(\frac{dp[j_2]}{sumc[j_2]-sumc[j_1]} \le t[i]+s\)
斜率就这样推出来啦！
注意题目中\(T[i]\)是有可能为负数的，所以\(t[i]\)不是单调递增的
所以我们就不能随意把队首元素删除，而在找队首时只能用二分
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=3e5+10;
int n,head,tail;
ll s,T[maxn],t[maxn],c[maxn],sumc[maxn];
ll G[maxn],dp[maxn];
int dq[maxn*2];
int find(ll x){
if(head==tail) return head;
int l=head,r=tail;
while(l<r){
int mid=(l+r)>>1;
if(dp[dq[mid+1]]-dp[dq[mid]]<=(x+s)*(sumc[dq[mid+1]]-sumc[dq[mid]])) l=mid+1;
else r=mid;
}
return l;
}
int main(){
/*2023.5.1 hewanying P5785 [SDOI2012]任务安排 斜率优化dp*/
scanf("%d%lld",&n,&s);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&T[i],&c[i]);
sumc[i]=sumc[i-1]+c[i];
t[i]=t[i-1]+T[i];
G[i]=t[i]*sumc[i];
}
memset(dp,0x3f,sizeof(dp));dp[0]=0;
for(int i=1;i<=n;i++){
int op=find(t[i]);
dp[i]=dp[dq[op]]+s*(sumc[n]-sumc[dq[op]])-t[i]*sumc[dq[op]]+G[i];
while(head<tail&&(dp[dq[tail]]-dp[dq[tail-1]])*(sumc[i]-sumc[dq[tail]])>=(dp[i]-dp[dq[tail]])*(sumc[dq[tail]]-sumc[dq[tail-1]]))
tail--; //这个地方必须要取>=在=时不用压入队中，否则会影响二分的进行，二分涉及相等的问题
dq[++tail]=i;
}
printf("%lld\n",dp[n]);
return 0;
}
总结
- 斜率优化还是存在精度问题，这道题就有两斜率相等的情况，所以直接变除为乘
- 在\(t[i]\)递增时才能用双端队列直接把队首删去，而这道题数组中存在负数，就只有用二分来计算
- 在dp开始前，不用加\(dq[++tail]=0\)，因为初始化中\(dq[0]=0\)，这样一来dq中就有两个0了
- 在删除队尾时，两斜率相等也是不满足条件的，所以要用\(>=\)
如果等于没有排除，会影响二分的进行