BZOJ1096: [ZJOI2007]仓库建设【斜率优化】

dzy posted @ 2013年6月24日 09:48 in BZOJ with tags BZOJ DP 斜率优化 , 1709 阅读

只是来除个草。。

这和当年CH上某cf赛制的题的B题很像。不过是这个的弱化版。

令f[i]表示第i个上面建仓库,1~i的都处理好了之后的最小花费。

那么f[i]=min{f[j]+w(j,i)}+c[i]

然后把w(j,i)化开:=p[j]*(x[i]-x[j])+p[j+1]*(x[i]-x[j+1])+...+p[i]*(x[i]-x[i])

=x[i]*p[j..i]-p[j]*x[j]+p[j+1]*x[j+1]+...+p[i]*x[i]

很明显前后两项都可以用前缀和数组O(1)出来。sp[i]=p[1..i],spx[i]=p[1]*x[1]+..+p[i]*x[i]

可惜这样还是n^2的。n还是100w这么凶残。

那么考虑斜率优化。

把w(j,i)带进去。

f[i]=min{f[j]+x[i](sp[i]-sp[j])-spx[i]+spx[j]}+c[i];

可以发现决策有单调性,x=sp[i]-sp[j],y=f[j]-spx[i]+spx[j],k=x[i]。那么就行了。O(n)

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double D;
const int maxn=1000005;
const double inf=1e30;
ll x[maxn],p[maxn],c[maxn],sp[maxn],spx[maxn],q[maxn],f[maxn];
inline D slope(int i,int j){
    ll dx=sp[i]-sp[j],dy=f[i]-f[j]+spx[i]-spx[j];
    if(!dx) return (dy>=0)?inf:-inf;
    return (D)dy/(D)dx;
}inline void read(ll &x){
    ll r=0,f=1;char ch;
    for(ch=getchar();(ch!='-')&&(ch<'0'||ch>'9');ch=getchar());
    if(ch=='-') f=-1; else r=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())r=r*10+ch-48;
    x=r*f;
}int main(){
    ll n;read(n);
    for(ll i=1;i<=n;i++){
        read(x[i]);read(p[i]);read(c[i]);
        sp[i]=sp[i-1]+p[i];
        spx[i]=spx[i-1]+p[i]*x[i];
    }ll s=0,e=0;q[0]=0;
    for(ll i=1;i<=n;i++){
        while(s<e&&slope(q[s],q[s+1])<=(D)x[i])s++;
        f[i]=f[q[s]]+x[i]*(sp[i]-sp[q[s]])-(spx[i]-spx[q[s]])+c[i];
        while(s<e&&slope(q[e],q[e-1])>=slope(i,q[e]))e--;
        q[++e]=i;
    }printf("%lld\n",f[n]);
    return 0;
}
Avatar_small
Alyssa 说:
2023年2月01日 19:31

This BZOJ1096 problem from the ZJOI2007 competition is an interesting challenge that tests the knowledge of slope optimization. It involves constructing a warehouse engagement rings to maximize the total area and presents an opportunity for readers to sharpen their skills in this particular topic. With careful analysis and planning, readers can come up with an optimal solution to this problem.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter