bzoj 2726 任务安排(3)/loj 10184-10186 斜率优化

任务安排1

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=;

int n,s,t[N],c[N],f[N];

int sumt[N],sumc[N];

signed main(){

    scanf("%lld%lld",&n,&s);

    for(int i=;i<=n;i++) scanf("%lld%lld",&t[i],&c[i]),sumt[i]=sumt[i-]+t[i],sumc[i]=sumc[i-]+c[i];

    memset(f,,sizeof f);

    f[]=;

    for(int i=;i<=n;i++){

        for(int j=;j<i;j++)

        f[i]=min(f[i],f[j]+(sumc[i]-sumc[j])*sumt[i]+s*(sumc[n]-sumc[j]));

        //利用刷表法，将影响向后累加

    }

    printf("%lld\n",f[n]);return ;

}

任务安排2 数据规模变大

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int N=;

long long f[N],sumt[N],sumc[N];

int q[N],n,s;

int main(){

    scanf("%d%d",&n,&s);

    for(int i=;i<=n;i++){

        int t,c;

        scanf("%d%d",&t,&c);

        sumt[i]=sumt[i-]+t;

        sumc[i]=sumc[i-]+c;

    }

    memset(f,0x3f,sizeof f);

    f[]=;

    int head=,tail=;

    q[]=;

    for(int i=;i<=n;i++){

        while(head<tail&&f[q[head+]]-f[q[head]]<=(s+sumt[i])*(sumc[q[head+]]-sumc[q[head]])) head++;

        f[i]=f[q[head]]-(sumt[i]+s)*sumc[q[head]]+s*sumc[n]+sumt[i]*sumc[i];

        while(head<tail&&(f[q[tail]]-f[q[tail-]])*(sumc[i]-sumc[q[tail]])>=(f[i]-f[q[tail]])*(sumc[q[tail]]-sumc[q[tail-]])) tail--;

        q[++tail]=i;

    }

    printf("%d\n",f[n]);return ;

}

任务安排3 T可能是负数

#include<bits/stdc++.h>

using namespace std;

const int N=;

long long sumt[N],sumc[N],f[N];

int q[N],n,s,head,tail;

int binarysearch(int i,int k){

    if(head==tail) return q[head];

    int l=head,r=tail;

    while(l<r){

        int mid=(l+r)>>;

        if(f[q[mid+]]-f[q[mid]]<=k*(sumc[q[mid+]]-sumc[q[mid]])) l=mid+;

        else r=mid;

    }return q[l];

}

int main(){

    cin>>n>>s;

    for(int i=;i<=n;i++){

        int t,c;

        cin>>t>>c;

        sumc[i]=sumc[i-]+c;

        sumt[i]=sumt[i-]+t;

    }

    head=tail=;

    for(int i=;i<=n;i++){

        int p=binarysearch(i,s+sumt[i]);

        f[i]=f[p]-(s+sumt[i])*sumc[p]+sumt[i]*sumc[i]+s*sumc[n];

        while(head<tail&&(f[q[tail]]-f[q[tail-]])*(sumc[i]-sumc[q[tail]])>=(f[i]-f[q[tail]])*(sumc[q[tail]]-sumc[q[tail-]])) tail--;

        q[++tail]=i;

    }

    cout<<f[n]<<endl;

    return ;

}