真的是假的吗?

P2605 【[ZJOI2010]基站选址】
DP

线段树优化DP好恶心

题意 :有 $n$ 个村庄,每个村庄距离1村庄 $d[i]$ ,要求建立不多于 $k$ 个基站,在第i个村庄建基站的费用为 $c[i]$ ,如果在距离村i不超过 $s[i]$ 内有基站则该村被覆盖,村i不被覆盖则需要赔偿该村 $w[i]$ ,求最少花费

然后显然是DP

就肥肠开心的用 $f[i][j]$ 表示到 $i$ 村庄建了 $j$ 个村庄的最小花费

转移方程为 $f[i][j] = max(f[i][j] , f[k][j - 1] + c[i] + cost(i , k))$

然后时间复杂度就炸了

然后我们发现第二维的j没啥卵用可以滚动掉

然而并没有用

考虑用线段树优化

$st[i]$ , $ed[i]$ 表示在 $st[i]$ ~ $ ed[i]$ 间只要有一个基站点i就不需要被赔偿

先单独处理下k = 1的情况

然后我们用线段树维护 $f[]$ 数组

之后我们第一层枚举建几座基站

每次枚举都要重新按照 $f[]$ 数组重新建树

之后我们每次查询这个点之前的f[]数组的最小值并+c[j]

然后我们看有没有某些城市恰可以被i覆盖到而不能被i+1覆盖到的,如果有则将1~st-1都加上该城市的赔偿费

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
# define LL long long
const int M = 20005 ;
const int INF = 1147000000 ;
using namespace std ;
inline int read(){
    char c = getchar();  int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9') {x = x * 10 + c - '0' ; c = getchar() ; }
    return x*w ;
}

int n , m ;
int w[M] , dis[M] , c[M] , s[M] ;
int st[M] , ed[M] ;
vector < int > p[M] ;
LL f[M] ;
LL tmin[M<<2] ;
int tag[M<<2] ;
# define ls now<<1
# define rs now<<1|1

inline void pushup(int now){
    tmin[now] = min(tmin[ls] , tmin[rs]) ;
}

void Build(int l , int r , int now){
    tag[now] = 0 ;
    if(l == r) {
        tmin[now] = f[l] ;
        return ;
    }
    int mid = (l + r)>>1 ;
    Build(l , mid , ls) ;
    Build(mid + 1 , r , rs) ;
    pushup(now) ;
}

inline void pushdown(int now){
    if(tag[now]){
        tag[ls] += tag[now] ;
        tag[rs] += tag[now] ;
        tmin[ls] += tag[now] ;
        tmin[rs] += tag[now] ;
        tag[now] = 0 ;
    }
}
void Change(int L , int R , int l , int r , int x , int now){
    if(L > R) return ;
    if(l >= L&& r<= R){
        tmin[now] += x ;
        tag[now] += x ;
        return ;
    }
    pushdown(now) ;
    int mid = (l + r)>>1 ;
    if(mid >= R) Change(L , R , l , mid , x , ls) ;
    else if(mid < L) Change(L , R , mid + 1 , r , x , rs) ;
    else{
        Change(L , mid , l , mid , x , ls) ;
        Change(mid + 1 , R , mid + 1 , r , x , rs) ;
    }
    pushup(now) ;
}
int query(int L , int R , int l , int r , int now){
    if(l > R|| r < L) return INF ;
    if(l >= L && r<= R) return tmin[now] ;
    int mid = (l + r)>>1 ;
    pushdown(now) ;
    if(mid >= R) return query(L , R , l , mid , ls) ;
    else if(mid < L) return query(L , R , mid + 1 , r , rs) ;
    else return min(query(L , mid , l , mid , ls) , query(mid + 1 , R , mid + 1 , r , rs)) ;
}
# undef ls 
# undef rs

LL Solve(){
    LL Ans = 0 , temp = 0 ;
    for(int i=1;i<=n;i++){
        f[i] = temp + c[i] ;
        for(int j=0;j<p[i].size();j++)
          temp += w[p[i][j]] ;
    }
    Ans = f[n] ;
    for(int i=2;i<=m;i++){
        Build(1 , n , 1) ;
        for(int j=1;j<=n;j++){
            f[j] = query(1 , j - 1 , 1 , n , 1) + c[j] ;
            for(int k = 0 ; k < p[j].size() ; k ++ ){
                int x = p[j][k] ;
                Change(1 , st[x] - 1 , 1 , n , w[x] , 1) ;
            }
        }
        Ans = min(Ans , f[n]) ;
    }
    return Ans ;
}
int main(){
    n = read() ; m = read() ;
    for(int i=2 ; i<=n ; i++) dis[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 , ++m ; dis[n] = w[n] = INF ; 
    for(int i=1 ; i<=n ; i++){
        int l = dis[i] - s[i] , r = dis[i] + s[i] ;
        st[i] = lower_bound(dis + 1 , dis + n + 1 , l) - dis ;
        ed[i] = lower_bound(dis + 1 , dis + n + 1 , r) - dis ;
        while(dis[i] + s[i] < dis[ed[i]]) --ed[i] ;
        p[ed[i]].push_back(i) ;
    }
    cout << Solve() << endl ;
    return 0 ;
}
评论