A simple Blog for wyx I've been down the bottle hoping.
BZOJ 1835: [ZJOI2010]base 基站选址 dp + 线段树优化
发表于: | 分类: Oi | 评论:0 | 阅读:60

浙江题里面最可做的一道QwQ

首先你需要一个$O(n^2*K)$的$dp$

$f(i,j)$ 表示当前基站是第$j$个基站,然后他建在了位置$i$

显然有一个通俗易懂的转移方程$f(i,j) = f(k,j-1)+calc(j+1,i-1)$

$calc(j+1,i-1)$表示$i,j$建设了基站但是中间不能覆盖到的点的权值和

然后考虑优化

我们考虑在$dp$的时候先循环第二维,也就是先确定这是第几个基站,然后再考虑建在哪就行了

我们先把每个位置的左右端点搞出来,然后找到最后一个位置$ed_i$使得在$ed_i$建设基站可以覆盖$i$,但是$ed_i+1$不能覆盖
同理处理出$st_i$,表示最靠前的那个

问题好像解决了,考虑从$i$转移到$i+1$,我们只需要考虑$ed_x = i$的点,以为这些点我现在建设基站已经无法覆盖了

对应的做出的更新就是$[1,st_x-1]$这些点的费用增加了$w[x]$

然后我们巧妙地把dp式子化成了$1d1d$问题!

线段树处理区间加和及区间最小值即可

不过好像这个东西就有决策单调了?没仔细研究,不过看起来是有的

然后需要注意的一点,记得在每次建树的时候把$lazy$清空

#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define pb push_back
typedef long long LL;
const int N = 1e5+5;
const int M = N << 2;
const int inf = 1e9;

LL read() {
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int n, K;
LL F[N], d[N], c[N], s[N], w[N];
int st[N], ed[N];

vector <LL> ep[N];
LL tr[M],lazy[M];
#define updata(k) tr[k] = min(tr[k<<1],tr[k<<1|1]) 

inline void build(int k,int l,int r) {
    if(l==r) {
        tr[k] = F[l];
        return;
    }
    lazy[k] = 0;
    tr[k] = inf;
    int mid = (l+r) >> 1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    updata(k);
}

inline void down(int k,int l,int r) {
    if(!lazy[k] || l == r) return;
    LL tt = lazy[k]; lazy[k] = 0; 
    lazy[k<<1] += tt; lazy[k<<1|1] += tt;
    tr[k<<1] += tt, tr[k<<1|1] += tt;
}

inline void change(int k,int l,int r,int x,int y,LL val) {
    if(x>y)return;
    if(l==x && r==y) {
        tr[k] += val;
        lazy[k] += val;
        return;
    }
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(y <= mid) change(k<<1,l,mid,x,y,val);
    else if(x > mid) change(k<<1|1,mid+1,r,x,y,val);
    else change(k<<1,l,mid,x,mid,val), change(k<<1|1,mid+1,r,mid+1,y,val);
    tr[k] = min(tr[k<<1],tr[k<<1|1]);
}

LL ask(int k,int l,int r,int x,int y) {
    if(x > y) return 0;
    if(l==x&& r==y) return tr[k];
    int mid = (l+r) >> 1;
    down(k,l,r);
    if(y <= mid)return ask(k<<1,l,mid,x,y);
    else if(x > mid)return ask(k<<1|1,mid+1,r,x,y);
    else return min(ask(k<<1,l,mid,x,mid),ask(k<<1|1,mid+1,r,mid+1,y));
}

int main() {
    n = read(), K = read();
    for(int i=2;i<=n;++i) d[i] = read();
    for(int i=1;i<=n;++i) c[i] = read();
    for(int i=1;i<=n;++i) s[i] = read();
    for(int i=1;i<=n;++i) w[i] = read();
    n ++, K ++; d[n] = inf, w[n] = inf;
    for(int i=1;i<=n;++i) {
        int l = d[i] - s[i], r = d[i] + s[i];
        l = lower_bound(d+1,d+n+1,l)-d;
        r = lower_bound(d+1,d+n+1,r)-d;
        if(d[i] + s[i] < d[r])  r--;
        st[i] = l, ed[i] = r;
        ep[ed[i]].pb(i);
    }
    LL ans , tmp = 0;
    vector <LL> :: iterator it;
    for(int i=1;i<=n;++i) {
        F[i] = tmp + c[i];
        for(it = ep[i].begin(); it != ep[i].end(); ++it) tmp += w[*it];
    }
    ans = F[n];
    for(int j=2;j<=K;++j) {
        build(1,1,n);
        for(int i=1;i<=n;++i) {
            F[i] = ask(1,1,n,1,i-1) + c[i];
            for(it = ep[i].begin(); it != ep[i].end(); ++it) change(1,1,n,1,st[(*it)]-1,w[(*it)]);
        }
        ans = min(ans,F[n]);
    }
    cout << ans << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP