学步园

/*
 * poj1180 AC
 * 动态规划+斜率优化+单调队列
 * 注意边界的处理，由于STL的问题导致浪费了很多时间。
 * 状态方程巧妙，逆序的方式很有效。
 *
 * 方程的变化十分巧妙。
 * 之前的方程：
 * dp[i][j] 表示前i的工作分成j组的最小花费。
 * f[i]表示前i个工作的费用系数和。
 * t[i]表示前i个工作的时间总和。
 * dp[i][j] = min(dp[k][j-1]+(s*j+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;
}