bzoj 2726 任务安排 斜率优化DP

这个题目中 斜率优化DP相当于存在一个 y = kx + z

然后给定 n 个对点 (x，y)  然后给你一个k， 要求你维护出这个z最小是多少。

那么对于给定的点来说 我们可以维护出一个下凸壳，因为如果存在一个上突壳的话，那么上突壳的点是一定不会被选上的。

所以对于解来说，只有下凸壳的点再会被选到。

所以我们就可以用单调队列维护处这个下凸壳。

假如我们保证给定的k是单调递增的， 那么我们就可以把前面一段不需要的东西给删掉。

假如k不是单调的，则我们就可以用二分找到第一个 >  询问k的答案。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 3e5 + ;

LL F[N], sumt[N], sumc[N];

int q[N];

int L = , R = ;

int solve(LL tmp){

    if(L == R) return L;

    int l = L, r = R - ;

    while(l <= r){

        int m = l+r >> ;

        if(F[q[m+]] - F[q[m]] <= (tmp)*(sumc[q[m+]]-sumc[q[m]])) l = m+;

        else r = m-;

    }

    return l;

}

int main(){

    int n, s;

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

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

        scanf("%lld%lld", &sumt[i], &sumc[i]);

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

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

    }

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

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

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

        while(L < R && ((F[q[R]]-F[q[R-]])*(sumc[i]-sumc[q[R]]) >= (F[i]-F[q[R]])*(sumc[q[R]]-sumc[q[R-]]))) R--;

        q[++R] = i;

    }

    cout << F[n] << endl;

    return ;

}