萌新求助 斜率优化DP 55分
查看原帖
萌新求助 斜率优化DP 55分
316322
hzoi_liuchang楼主2020/7/22 06:58
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
ll f[maxn],q[maxn],sumt[maxn],sumc[maxn],t[maxn],c[maxn];
ll n,s,head=1,tail=0;
double getx(ll aa){
    return (double)sumc[aa];
}
double gety(ll aa){
    return (double)f[aa];
}
double xl(int k,int j){
    if(getx(k)==getx(j)){
        if(gety(k)>=gety(j)) return 1e8;
        else return -1e8;
    }
    return (gety(k)-gety(j))/(getx(k)-getx(j));
}
ll ef(ll now){
    if(head==tail) return q[head];
    ll l=head,r=tail;
    while(l<r){
        ll mids=(l+r)>>1;
        if(xl(q[mids],q[mids+1])<now) l=mids+1;
        else r=mids;
    }    
    return q[l];
}
int main(){
    scanf("%lld%lld",&n,&s);
    for(ll i=1;i<=n;i++){
        scanf("%lld%lld",&t[i],&c[i]);
        sumt[i]=sumt[i-1]+t[i];
        sumc[i]=sumc[i-1]+c[i];
    }
    q[++tail]=0;
    for(ll i=1;i<=n;i++){
        ll t=ef(s+sumt[i]);
        f[i]=f[t]+sumt[i]*(sumc[i]-sumc[t])+s*(sumc[n]-sumc[t]);
        while(head<tail && xl(q[tail-1],q[tail])>=xl(q[tail],i)) tail--;
        q[++tail]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

2020/7/22 06:58
加载中...