【题目链接】 

 

【题目大意】

　　N个任务排成一个序列在一台机器上等待完成（顺序不得改变），

　　这N个任务被分成若干批，每批包含相邻的若干任务。

　　从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。

　　在每批任务开始前，机器需要启动时间S，

　　而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

　　每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小

 

【题解】

　　我们可以得到dp方程dp[i]=min{dp[j]+(sumT[i]-sumT[j]+S)*(sumF[n]-sumF[j])}

　　dp[i]=(sumF[n]-sumF[j])*sumT[i]+dp[j]+(S-sumT[j])*(sumF[n]-sumF[j])

　　是关于sumT[i]的一元一次方程，我们对此做斜率优化。

 

【代码】

#include 
     
      #include 
      
       #include 
       
        typedef long long LL;const int MAX_N=10010;int n;LL k,a[MAX_N],b[MAX_N],dp[MAX_N],S[MAX_N],F[MAX_N],deq[MAX_N];LL f(int x,int y){return (F[n]-F[x])*S[y]+dp[x]+(k-S[x])*(F[n]-F[x]);}bool check(int f1,int f2,int f3){    LL a1=F[n]-F[f1],b1=dp[f1]+(k-S[f1])*(F[n]-F[f1]);    LL a2=F[n]-F[f2],b2=dp[f2]+(k-S[f2])*(F[n]-F[f2]);    LL a3=F[n]-F[f3],b3=dp[f3]+(k-S[f3])*(F[n]-F[f3]);    return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2);}void solve(){    for(int i=0;i
        
         =f(deq[s+1],i))s++;        dp[i]=f(deq[s],i);        while(s+1