POJ - 1180 Batch Scheduling（斜率优化DP）
#include<cstdio>typedef long long LL;
const int N = 300010;
LL sc[N], st[N], f[N];
int q[N], hh, tt;int main()
{
int n, s; scanf("%d%d", &n, &s);for (int i = 1; i <= n; i ++ ){
scanf("%lld%lld", &st[i], &sc[i]);st[i] += st[i - 1];sc[i] += sc[i - 1];}hh = 0, tt = 0;for (int i = 1; i <= n; i ++ ){
while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <=(st[i] + s) * (sc[q[hh + 1]] - sc[q[hh]])) hh ++ ;f[i] = f[q[hh]] - (st[i] + s) * sc[q[hh]] + sc[i] * st[i] + s * sc[n];while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (sc[i] - sc[q[tt]]) >=(f[i] - f[q[tt]]) * (sc[q[tt]] - sc[q[tt - 1]])) tt -- ;q[ ++ tt] = i;}printf("%lld\n", f[n]);return 0;
}