题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2726
倒着做,前面的点对后面的点都是有贡献的。 f[i]=min(f[j]+cost[i]*(T[i]-T[j]+S)) (j>i)
然后。。。。时间可以是负数的。(所以看起来好好的单调队列+斜率优化就变成了动态凸包。。x坐标并不是有序的。。
用cdq分治处理。。
(看起来是要逆序维护下凸包的。但是我比较蠢于是把序列翻转了一下这样就变成了正着做下凸包辣。。
然后时间是负数的话,不等号的方向要改变。
(虽然我在写的时候脑子一团浆糊。。但是感觉写出来的代码还不会太乱吧。。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define maxn 300500
#define inf int(1e9)
#define ll long long
using namespace std;
struct data{int x,k,id;ll y;
}a[maxn],s[maxn],t[maxn];
int n,S;
ll f[maxn],bin[];
int cross(data a,data b,data c){
int x1=b.x-a.x,x2=c.x-a.x;
ll y1=b.y-a.y,y2=c.y-a.y;
if ((x1<)^(x2<)) return y1*x2<=y2*x1;
else return x1*y2-x2*y1<=;
}
bool jud(data a,data b,int k){
ll x=b.x-a.x,y=b.y-a.y;
if (x<) return y>x*k;
else return y<x*k;
}
int read(){
int x=,f=; char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)){x=x*+ch-''; ch=getchar();}
return x*f;
}
void cdq(int l,int r){
if (l==r) {
a[l].y=f[l];
return;
}
int l1=l,l2=(l+r)/+,mid=(l+r)/;
rep(i,l,r) if (a[i].id<=mid) t[l1++]=a[i]; else t[l2++]=a[i];
rep(i,l,r) a[i]=t[i];
cdq(l,mid);
int top=;
rep(i,l,mid){
while (top>&&cross(s[top-],s[top],a[i])) top--;
s[++top]=a[i];
}
int j=;
rep(i,mid+,r){
while (j<top&&jud(s[j],s[j+],a[i].k)) j++;
f[a[i].id]=min(f[a[i].id],1LL*a[i].k*(a[i].x-s[j].x+S)+f[s[j].id]);
}
cdq(mid+,r);
l1=l,l2=mid+;
rep(i,l,r) if (l1<=mid&&(a[l1].x<a[l2].x||l2>r)) t[i]=a[l1++]; else t[i]=a[l2++];
rep(i,l,r) a[i]=t[i];
}
int main(){
n=read(); S=read();
rep(i,,n) a[i].x=read(),a[i].k=read();
down(i,n,) a[i].x+=a[i+].x,a[i].k+=a[i+].k;
rep(i,,n/) swap(a[i],a[n-i+]);
rep(i,,n) f[i]=1LL*a[i].k*(a[i].x+S),a[i].id=i; f[]=;
cdq(,n);
printf("%lld\n",f[n]);
return ;
}