題目傳送門
這題和bzoj1492Cash幾乎一樣，是以這裡隻貼公式。
f[i]=min(f[j]+c[j]∗(t[i]−t[j]+s)) f [ i ] = m i n ( f [ j ] + c [ j ] ∗ ( t [ i ] − t [ j ] + s ) )
=> f[k]+c[k]∗t[i]−c[k]∗(t[k]−s)<=f[j]+c[j]∗t[i]−c[j]∗(t[j]−s) f [ k ] + c [ k ] ∗ t [ i ] − c [ k ] ∗ ( t [ k ] − s ) <= f [ j ] + c [ j ] ∗ t [ i ] − c [ j ] ∗ ( t [ j ] − s )
=> f[k]+c[k]∗t[i]−c[k]∗t[k]+c[k]∗s<=f[j]+c[j]∗t[i]−c[j]∗t[j]+c[j]∗s f [ k ] + c [ k ] ∗ t [ i ] − c [ k ] ∗ t [ k ] + c [ k ] ∗ s <= f [ j ] + c [ j ] ∗ t [ i ] − c [ j ] ∗ t [ j ] + c [ j ] ∗ s
=> (f[k]−c[k]∗t[k]+c[k]∗s)−(f[j]−c[j]∗t[j]+c[j]∗s)<=(c[j]−c[k])∗t[i] ( f [ k ] − c [ k ] ∗ t [ k ] + c [ k ] ∗ s ) − ( f [ j ] − c [ j ] ∗ t [ j ] + c [ j ] ∗ s ) <= ( c [ j ] − c [ k ] ) ∗ t [ i ]
=> ((f[k]−c[k]∗t[k]+c[k]∗s)−(f[j]−c[j]∗t[j]+c[j]∗s))/(c[j]−c[k])<=t[i] ( ( f [ k ] − c [ k ] ∗ t [ k ] + c [ k ] ∗ s ) − ( f [ j ] − c [ j ] ∗ t [ j ] + c [ j ] ∗ s ) ) / ( c [ j ] − c [ k ] ) <= t [ i ]
然後用cdq分治優化即可。
細節詳見代碼。
#include<cstdio>
#include<cmath>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N=;
int n,q[N];
ll s,f[N];
struct data{
ll t,c;
int id;
friend bool operator < (const data &a,const data &b){
return a.t<b.t;
}
}a[N],b[N];
inline int rd(){
register int res=,f=;
register char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
res=res*+ch-'0';
ch=getchar();
}
return res*f;
}
ll get(int i){
return f[a[i].id]-a[i].c*a[i].t+a[i].c*s;
}
ll getx(int j,int k){
return get(k)-get(j);
}
ll gety(int j,int k){
return a[j].c-a[k].c;
}
void solve(int l,int r){
if(l==r){
return;
}
register int mid=(l+r)/,j=l,k=mid+;
for(register int i=l;i<=r;i++){
if(a[i].id<=mid){
b[j++]=a[i];
}else{
b[k++]=a[i];
}
}
for(register int i=l;i<=r;i++){
a[i]=b[i];
}
solve(l,mid);
j=,k=;
for(register int i=l;i<=mid;i++){
while(j<k&&getx(q[k],i)*gety(q[k-],q[k])<getx(q[k-],q[k])*gety(q[k],i)){
k--;
}
q[++k]=i;
}
for(register int i=mid+;i<=r;i++){
while(j<k&&getx(q[j],q[j+])<=a[i].t*gety(q[j],q[j+])){
j++;
}
if(j<=k){
f[a[i].id]=min(f[a[i].id],f[a[q[j]].id]+a[q[j]].c*(a[i].t-a[q[j]].t+s));
}
}
solve(mid+,r);
j=l,k=mid+;
for(register int i=l;i<=r;i++){
if(j<=mid&&(k>r||a[j].c>=a[k].c)){
b[i]=a[j++];
}else{
b[i]=a[k++];
}
}
for(register int i=l;i<=r;i++){
a[i]=b[i];
}
}
signed main(){
scanf("%d%lld",&n,&s);
for(register int i=;i<=n;i++){
scanf("%lld%lld",&a[i].t,&a[i].c);
a[i].t+=a[i-].t;
a[i].c+=a[i-].c;
a[i].id=i;
}
ll tmp=a[n].c;
for(register int i=n;i>=;i--){
a[i].c=tmp-a[i].c;
}
for(register int i=;i<=n;i++){
f[i]=a[].c*(a[i].t+s);
}
sort(a+,a+n+);
solve(,n);
printf("%lld",f[n]);
return ;
}