题解 P2120 【[ZJOI2007]仓库建设】

· · 题解

背景：

做法：

首先，先把 dp 式子推出来：

设 {f_i} 为 在 { i } 处建立基地的情况下，从 {1} 处理到 { i } 时的最小总代价。

那么有 { f_i = \min \limits_{ 0 \le j < i } \left \{ { { f_j + x_i \times \sum \limits_{ l=j+1 } ^ {i}{p_l} } - \sum \limits_{ l=j+1 } ^ { i } { x_l \times p_l } } \right \} + c_i } 。

然后，考虑前缀和优化。记 {sump_i} 为 {p_i} 的前缀和， {sum_i} 为 { p_i \times x_i} 的前缀和。

那么 {f_i = \min \limits_{0 \le j < i} \left \{ f_j + x_i \times (sump_i - sump_j) - ( sum_i - sum_j ) \right \} + c_i} 。

展开，移项，考虑 {f_i} 与 {f_j} 的关系 ,可得 { f_j + sum_j = f_i - x_i \times sump_j - c_i } 。

将 ( sump_j , f_j + sum_j) 看作平面上的点。

然后就可以快乐地斜率优化了。

然后，你就知道背景是什么意思了。

这里膜拜出 Hack 数据的神，脑洞是真的大 。

我们还要考虑一种情况：若最后几处没有货物的话，不一定要在 {n} 处建立仓库。

我们应该从 {n} 往上找，直到找到 {p_i} 非零处，记为 {mem} 。

那么正确答案就是 { \min \limits_{ mem \le i \le n } { f_i} } 。

献上代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _for(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define For(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
#define INF 0x7fffffff
#define il inline
#define rg register
#define int ll
const int N=1e6+5;
int n;
ll sp[N],s[N],f[N];
int x[N],p[N],c[N],q[N],l,r;
#define Y(o) (f[o]+s[o])
#define X(o) (sp[o])
il double slope(rg int a,rg int b){
    if(X(b)==X(a)) return 1e18;
    return 1.0*(Y(b)-Y(a))/(X(b)-X(a));
}
signed main(){
    scanf("%d",&n);
    _for(i,1,n) scanf("%lld%lld%lld",x+i,p+i,c+i), sp[i]=sp[i-1]+p[i], s[i]=s[i-1]+x[i]*p[i];
    q[l=r=1]=0;
    _for(i,1,n){
        while(l<r and slope(q[l],q[l+1])<=(double)1.0*x[i]) ++l;
        rg int j(q[l]);
        f[i]=f[j]+sp[i]*x[i]-sp[j]*x[i]-s[i]+s[j]+1LL*c[i];
        while(l<r and slope(q[r-1],q[r])>=slope(q[r],i)) --r;
        q[++r]=i;
    }
    rg int mem(n);
    while(!p[mem] and mem) --mem;
    if(!mem) return puts("0"), 0;
    rg ll ans(1e18);
    _for(i,mem,n) ans=min(ans,f[i]);
    return printf("%lld\n",ans),0;
}