动态规划+斜率优化+单调队列 注意边界的处理，由于STL的问题导致浪费了很多时间。 状态方程巧妙，逆序的方式很有效。

方程的变化十分巧妙。 之前的方程： dp[i][j] 表示前i的工作分成j组的最小花费。 f[i]表示前i个工作的费用系数和。 t[i]表示前i个工作的时间总和。 dp[i][j] = min(dp[k][j-1]+(sj+t[i]-t[k])(f[i]-f[k]))

改进的方程： f[i][j]中j这一维应该被消除。 考虑在顺序处理时，工作k1与工作k2(k1<k2)，处理k2时的总时间包含了k1的时间，类似于每次做覆盖线段的操作，每次都要从头覆盖。 所以当从n开始逆序处理时，每次都只用处理当前段，而之后的费用自动累加。 巧妙的设计，值得研究。

dp[i]表示倒数前i个工作的最小花费。 f[i]表示倒数前i个工作的费用系数和。 t[i]表示倒数前i个工作的时间总和。 dp[i] = min(dp[j]+(s+t[i]-t[j])*f[i])

斜率优化： 对k1>k2，得到的f[i]分别为g[k1],g[k2]有 g[k1]-g[k2] = dp[k1]-dp[k2]-(t[k1]-t[k2])*f[i] 当g[k1]-g[k2]<0时，k1优于k2。 又由于f[i]为单调增加函数，所以当slope[k1,k2]=(dp[k1]-dp[k2])/(t[k1]-t[k2])>f[i]时，g[k1]始终优于g[k2]。

所以有单调队列，保证slope[q1,q2]<slope[q2,q3]<slope[q3,q4]...，则每次最优解均为q1。 算法流程： 1.对于阶段i有f[i]，首先从头扫描队列，如果slope[q[i],q[i+1]]<=f[i]则队头出队 (由于slope<=f[i]时q[i]一定不如q[i+1]更优)，直到不满足为止。 这保证了队列中所有的slope[q[i],q[i+1]]>f[i] 2.队首出队，计算dp[i] = dp[q1]+(s+t[i]-t[q1])*f[i];

• 3.i需要入队，从队尾开始扫描，如果slope[q[n-1],q[n]]>=slope[q[n],i]，则队尾出队 (这一条满足了slope递增的性质),直到不满足为止。

#include<cstdio>
#include<algorithm>
#include<deque>
#define INF (1<<30)
#define N 10005
using namespace std;

int t[10005],f[10005];
long dp[10005];
int que[N];
long head,tail,sumq;
int main()
{
	int n,s,i,k1,k2;
	//    FILE* fin = fopen("d.in","r");
	//    FILE* fout = fopen("d.out","w");
	scanf("%d%d",&n,&s);
	//    fscanf(fin,"%d%d",&n,&s);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&t[i],&f[i]);
		//        fscanf(fin,"%d%d",&t[i],&f[i]);
		dp[i] = INF;
	}
	for(i=n-1;i>=1;i--)
		f[i] += f[i+1],t[i] += t[i+1];
	
	dp[n] = (s+t[n])*f[n];
	head = sumq = 0,tail = -1;
	que[++tail] = n,sumq++;
	for(i=n-1;i>=1;i--)
	{
		while(sumq>1)
		{
			k1 = que[head];
			k2 = que[(head+1+N)%N];
			if((dp[k1]-dp[k2])-(t[k1]-t[k2])*f[i]>=0) 
				head = (head+1+N)%N,sumq--;
			else break;
		}
		
		k1 = que[head];
		dp[i] = (s+t[i])*f[i];
		dp[i] = min(dp[i],dp[k1]+f[i]*(s+t[i]-t[k1]));
		
		while(sumq>1)
		{
			k1 = que[tail];
			k2 = que[(tail-1+N)%N];
			if((dp[i]-dp[k1])*(t[k1]-t[k2])<=(dp[k1]-dp[k2])*(t[i]-t[k1])) 
				tail = (tail-1+N)%N,sumq--;
			else break;
		}
		que[tail = (tail+1+N)%N] = i,sumq++;
	}
	
	printf("%ld\n",dp[1]);
	return 0;
}