[lnsyoj539/luoguP2120/ZJOI2007]仓库建设

标签：return int sum sump luoguP2120 lnsyoj539 ZJOI2007 include LL

题意

懒了（

sol

显然 DP
设计状态：\(f_i\) 表示 \(1\sim i\) 的工厂中，在第 \(i\) 个工厂处建设仓库的最小代价；
状态转移：由题意，显然可得：

\[f_i = \min_{j=1}^{i-1} \{f_j + c_i + \sum_{k=j+1}^i(x_i-x_k)\cdot p_k\} \]

我们发现中间的一坨求和可以通过前缀和的方式预处理出 \(sum_i=\sum_{j=1}^i x_i\cdot p_i\) 和 \(sump_i=\sum_{j=1}^i p_i\)，这样原式就转化为了

\[f_i = \min_{j=1}^{i-1} \{f_j + c_i + x_i \cdot (sump_i - sump_j) - (sum_i - sum_j)\} \]

时间复杂度 \(O(n^2)\)。
显然，我们可以将其进行斜率优化，具体参见[lnsyoj538/luoguP3628/APIO2010]特别行动队。本题与该题在优化上无明显区别，仅是将上凸包修改为了下凸包。
本题需要注意，由于在最后可能出现 \(p_i =0\) 的情况，因此我们需要将末尾所有的连续的 \(p_i=0\) 的结果求最小值即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long LL;

const int N = 1000005;

LL xx[N], sum[N], sump[N], c[N], f[N];
int n;
int q[N];

LL x(int u){
    return sump[u];
}

LL y(int u){
    return f[u] + sum[u];
}

double slope(int a, int b){
    return (double) (y(b) - y(a)) / (x(b) - x(a));
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d%d", &xx[i], &sump[i], &c[i]), sum[i] = sum[i - 1] + sump[i] * xx[i], sump[i] += sump[i - 1];
    
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ ){
        while (hh < tt && slope(q[hh], q[hh + 1]) <= xx[i]) hh ++ ;
        int j = q[hh];
        f[i] = f[j] - (sum[i] - sum[j]) + xx[i] * (sump[i] - sump[j]) + c[i];
        while (hh < tt && slope(q[tt], i) <= slope(q[tt - 1], q[tt])) tt -- ;
        q[ ++ tt] = i;
    }

    LL res = f[n];
    for (int i = n; i == n || sump[i + 1] == sump[i]; i -- ) res = min(f[i], res);

    printf("%lld\n", res);

    return 0;
}

标签：return,int,sum,sump,luoguP2120,lnsyoj539,ZJOI2007,include,LL
From： https://www.cnblogs.com/XiaoJuRuoUP/p/-/lnsyoj539_luoguP2120