题目大意：有n个任务，已知做每件任务所需的时间，并且每件任务都对应一个系数fi。现在，要将这n个任务分成若干个连续的组，每分成一个组的代价是完成这组任务所需的总时间加上一个常数S后再乘以这个区间的系数和。求最小代价。

题目分析：分组求最优值得问题。不过，这道题采用倒推可能要好做一些。定义状态dp(i)表示完成从第 i 个任务到第n个任务需要的最小代价，则状态转移方程为

dp(i)=min(dp(j)+(sumt(i)-sumt(j)+s)*sumf(i)，很显然的要用斜率优化。

 

代码如下：

# include
     
      # include
      
       # include
       
        # include
        
         using namespace std;# define LL long longconst int INF=1<<30;const int N=10005;int n,m;int q[N];int t[N];int f[N];int dp[N];void read(int &x){    char ch=' ';    while(ch<'0'||ch>'9')        ch=getchar();    x=0;    while(ch>='0'&&ch<='9'){        x=x*10+ch-'0';        ch=getchar();    }}void init(){    for(int i=0;i
         
          =0;--i){        t[i]+=t[i+1];        f[i]+=f[i+1];    }}double getK(int i,int j){    return (double)(dp[i]-dp[j])/(double)(t[i]-t[j]);}int toDp(int i,int j){    return dp[j]+(t[i]-t[j]+m)*f[i];}int solve(){    int head=0,tail=-1;    dp[n]=0;    q[++tail]=n;    for(int i=n-1;i>=0;--i){        while(head+1<=tail&&getK(q[head+1],q[head])<=(double)f[i])            ++head;        dp[i]=toDp(i,q[head]);        while(head+1<=tail&&getK(i,q[tail])<=getK(q[tail],q[tail-1]))            --tail;        q[++tail]=i;    }    return dp[0];}int main(){    while(~scanf("%d%d",&n,&m))    {        init();        printf("%d\n",solve());    }    return 0;}