[P5785 [SDOI2012]任务安排] 题解

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方程式了

斜率优化

1. 设两个决策点\(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]\)
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;
}

总结

1. 斜率优化还是存在精度问题，这道题就有两斜率相等的情况，所以直接变除为乘
2. 在\(t[i]\)递增时才能用双端队列直接把队首删去，而这道题数组中存在负数，就只有用二分来计算
3. 在dp开始前，不用加\(dq[++tail]=0\)，因为初始化中\(dq[0]=0\)，这样一来dq中就有两个0了
4. 在删除队尾时，两斜率相等也是不满足条件的，所以要用\(>=\)
   如果等于没有排除，会影响二分的进行