题意
N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i 个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完 成）。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。
算法讨论
毫无疑问DP.转移方程：dp[i]=Min{dp[j]+(sumF[i]-sumF[j])*sumT[i]+s*(sumF[N]-sumF[j])},其中dp[i]表示的是完成1~i的工作的花费+因为开机启动时间所浪费的后面的花费。
但是这个转移方程的复杂度是O（N^2）的，如果RP好的话可以试试~但是显然，我们有更强大的方法：斜率优化。
至于什么是斜率优化……可以百度一下“斜率优化”……
只说说这道题的证明：
设G[i,j]表示dp[i]的决策为j时的dp[i]值。
设j1<j2,且G[i,j1]<G[i,j2](即以j1为决策时优于j2)
G[i,j1]=dp[j1]-sumF[j1]*sumT[i]-s*sumF[j1]+s*sumF[N]+sumF[i]*sumT[i]
G[i,j2]=dp[j2]-sumF[j2]*sumT[i]-s*sumF[j2]+s*sumF[N]+sumF[i]*sumT[i]
G[i,j1]-G[i,j2]=(dp[j1]-s*sumF[j1])-(dp[j2]-s*sumF[j2])-sumT[i]*(sumF[j1]-sumF[j2])<0
整理得
【(dp[j1]-s*sumF[j1])-(dp[j2]-s*sumF[j2])】
--------------------------------------------------------------------- > sumT[i]
(sumF[j1]-sumF[j2])
又因为sumT[i]单调不降
所以最优决策单调
那么维护一个队列就可以了。
参考代码：
# include <iostream>
# include <cstdio>
# include <cmath>
using namespace std;
const int maxN=10005;
long long dp[maxN],f[maxN],t[maxN],N,s;
long long calc(int,int);
int slope(int,int,int);
int main()
{
int seq[maxN],fi,ti,l=1,r=1;
seq[1]=0;
scanf("%lld",&N);scanf("%lld",&s);
for (int i=1;i<=N;i++){
scanf("%d%d",&ti,&fi);t[i]=t[i-1]+ti;f[i]=f[i-1]+fi;
}
for (int i=1;i<=N;i++){
while ((l<r)&&(calc(i,seq[l])>calc(i,seq[l+1]))) l++;
dp[i]=calc(i,seq[l]);
while ((l<r)&&(slope(seq[r],seq[r-1],i))) r--;
seq[++r]=i;
}
printf("%lld\n",dp[N]);
return 0;
}
long long calc(int i,int j)
{
return dp[j]+(f[i]-f[j])*t[i]+s*(f[N]-f[j]);
}
int slope(int i,int j,int k)
{
long long imj=((dp[k]-s*f[k])-(dp[i]-s*f[i]))*(f[k]-f[j]);
long long jmi=((dp[k]-s*f[k])-(dp[j]-s*f[j]))*(f[k]-f[i]);
return imj<jmi;
}