E52 斜率优化DP [SDOI2012]任务安排

/*
dp[i]=min(dp[i],dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));

dp[i]=dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));

dp[i]-st[i]*sf[i]-s*sf[n]=  dp[j]-s*sf[j]- st[i]*sf[j]
dp[j]-s*sf[j] =st[i]*sf[j] + dp[i]-st[i]*sf[i]-s*sf[n]
yj=dp[j]-s*sf[j]
xj=sf[j]
k=st[i]
b=dp[i]-st[i]*sf[i]-s*sf[n]

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=310000;
LL dp[N],f[N],t[N],st[N],sf[N],s;int q[N];
double X(int j){ return 1.0*sf[j];}
double Y(int j){ return 1.0*(dp[j]-s*sf[j]);}
double K(int j1,int j2){ return  (X(j2)==X(j1))?1e18*( Y(j2)-Y(j1) ):( Y(j2)-Y(j1) ) / ( X(j2)-X(j1) )   ;}
int find(int l,int r,int i)
{
	while(l<r)
	{
		int mid=(l+r)/2;
		if(K(q[mid],q[mid+1])<=st[i])l=mid+1;
		else r=mid;
	}
	return r;
}

E52 斜率优化DP [SDOI2012]任务安排

/*
dp[i]=min(dp[i],dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));

dp[i]=dp[j]+st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));

dp[i]-st[i]*sf[i]-s*sf[n]=  dp[j]-s*sf[j]- st[i]*sf[j]
dp[j]-s*sf[j] =st[i]*sf[j] + dp[i]-st[i]*sf[i]-s*sf[n]
yj=dp[j]-s*sf[j]
xj=sf[j]
k=st[i]
b=dp[i]-st[i]*sf[i]-s*sf[n]

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=310000;
LL dp[N],f[N],t[N],st[N],sf[N],s;int q[N];
double X(int j){ return 1.0*sf[j];}
double Y(int j){ return 1.0*(dp[j]-s*sf[j]);}
double K(int j1,int j2){ return  (X(j2)==X(j1))?1e18*( Y(j2)-Y(j1) ):( Y(j2)-Y(j1) ) / ( X(j2)-X(j1) )   ;}
int find(int l,int r,int i)
{
	while(l<r)
	{
		int mid=(l+r)/2;
		if(K(q[mid],q[mid+1])<=st[i])l=mid+1;
		else r=mid;
	}
	return r;
}
int main()
{
    int n;scanf("%d%lld",&n,&s);
    st[0]=0;sf[0]=0; 
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&t[i],&f[i]);
        st[i]=st[i-1]+t[i];
        sf[i]=sf[i-1]+f[i];
    }
    int r=1;q[1]=0;dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        int l=find(1,r,i);
        dp[i]=dp[q[l]]+st[i]*(sf[i]-sf[q[l]])+s*(sf[n]-sf[q[l]]);
        while( l<r && K(q[r-1],q[r]) >= K(q[r],i) ) r--;
        q[++r]=i;    
    }
    printf("%lld\n",dp[n]);
    return 0;
}

李超线段树CODE（HDH）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
const ll D=2e8;
int n,rt;
ll s,t[N],c[N],sum[N],g[N],f[N];
struct node{
    int p,ls,rs,tag;
}tree[N];
struct line{
    ll k=1e9,b=1e9;
}lines[N];
int cnt;
bool cmp(ll x,int u,int v){
    return lines[ u ].k*x+lines[ u ].b<lines[v].k*x+lines[v].b;
}
void upd(int &p,ll pl,ll pr,int u){
    ll mid=(pl+pr)>>1;
    if(!p) p=++cnt;
    int &v=tree[p].tag;
    if(cmp(mid,u,v)) swap(u,v);
    if(pl==pr) return;
    if(cmp(pl,u,v)) upd(tree[p].ls,pl,mid,u);
    if(cmp(pr,u,v)) upd(tree[p].rs,mid+1,pr,u);
}
ll query(int p,ll pl,ll pr,ll x){
    int id=tree[p].tag;
    ll ret=lines[id].k*x+lines[id].b;
    if(pl==pr){
        return ret;
    }
    ll mid=(pl+pr)>>1;
    if(x<=mid)
        return min(query(tree[p].ls,pl,mid,x),ret);
    else
        return min(query(tree[p].rs,mid+1,pr,x),ret);
}
ll k(int i){
    return g[i];
}
ll b(int i){
    return -g[i]*D-g[i]*sum[i]+f[i]+g[i]*s;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;++i){
        cin>>t[i]>>c[i];
        sum[i]=sum[i-1]+t[i];
        g[i]=g[i-1]+c[i];
    }
    for(int i=0;i<=n;++i){
        g[i]=g[n]-g[i];
    }
    lines[n+1]={k(0),b(0)};
    upd(rt,1,2*D,n+1);
    for(int i=1;i<=n;++i){
        f[i]=query(rt,1,2*D,sum[i]+D);
        lines[i]={k(i),b(i)};
        upd(rt,1,2*D,i);
    }
    cout<<f[n];
    return 0;
}