题解:ZJOI2010基站选址 线段树+dp

庆祝通过noip2018初赛,系列五题EP4.

题目描述

有N个村庄坐落在一条直线上,第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站,在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站,那么就村庄被基站覆盖了。如果第i个村庄没有被覆盖,则需要向他们补偿,费用为Wi。现在的问题是,选择基站的位置,使得总费用最小。

输入输出格式

输入格式:

输入文件的第一行包含两个整数N,K,含义如上所述。

第二行包含N-1个整数,分别表示D2,D3,…,DN ,这N-1个数是递增的。

第三行包含N个整数,表示C1,C2,…CN。

第四行包含N个整数,表示S1,S2,…,SN。

第五行包含N个整数,表示W1,W2,…,WN。

输出格式:

输出文件中仅包含一个整数,表示最小的总费用。

输入输出样例

输入样例#1: 复制
3 2
1 2
2 3 2
1 1 0
10 20 30
输出样例#1: 复制
4

说明

40%的数据中,N<=500;

100%的数据中,K<=N,K<=100,N<=20,000,Di<=1000000000,Ci<=10000,Si<=1000000000,Wi<=10000。

解题思路:

dp[i][j]表示第i个村庄修第j个基站所需要的最小费用

写出dp方程:dp[i][j]=min{dp[i][j],dp[k][j-1]+cost(k,j)+c[i]}

可以把j循环滚动掉

在处理cost时运用邻接表技巧,之后发现决策点可以用线段树优化

(庆祝通过noip2018提高初赛第四题)

下面上代码:

  1#include<bits/stdc++.h>
2#define N 20005 
3#define int long long  
4using namespace std;
5int dp[N],n,m,x,y,z,k,c[N],s[N],w[N],d[N],lim,l[N],r[N],Head[N],tot,tag[N];
6struct Edge{
7    int to,nxt;
8}E[N*2];
9struct node{
10    int lazy,minn;
11}tree[4*N];
12void addedge(int x,int y){
13    E[++tot]=(Edge){y,Head[x]};
14    Head[x]=tot;
15}
16void build(int p,int l,int r){
17    tree[p].lazy=0;
18    if (l==r){
19        tree[p].minn=dp[l];
20        return;
21    }
22    int mid=l+r >> 1;
23    build(p<<1,l,mid);
24    build(p<<1|1,mid+1,r);
25    tree[p].minn=min(tree[p<<1].minn,tree[p<<1|1].minn); 
26}
27void Add(int p,int l,int r,int v){
28    tree[p].lazy+=v;
29    tree[p].minn+=v;
30
31void pushdown(int p,int l,int r,int mid){
32    if (tree[p].lazy==0return;
33    Add(p<<1,l,mid,tree[p].lazy);
34    Add(p<<1|1,mid+1,r,tree[p].lazy);
35    tree[p].lazy=0;
36}
37int query(int p,int l,int r,int x,int y){
38    if (l>=x&&r<=y) return tree[p].minn;
39    int mid=l+r >> 1;
40    if (l>r||r<x||l>y) return 0;
41    pushdown(p,l,r,mid);
42    int res=1023456789;
43    if (x<=mid) res=min(res,query(p<<1,l,mid,x,y));
44    if (y>mid) res=min(res,query(p<<1|1,mid+1,r,x,y));
45    return res;
46}
47void modify(int p,int l,int r,int x,int y,int v){
48    if (l>=x&&r<=y){
49        Add(p,l,r,v);
50//        tree[p].minn+=v;
51//        tree[p].lazy+=v;
52        return;
53    }
54    if (l>r||l>y||r<x) return;
55    int mid=l+r >> 1;
56    pushdown(p,l,r,mid);
57    if (x<=mid) modify(p<<1,l,mid,x,y,v);
58    if (y>mid) modify(p<<1|1,mid+1,r,x,y,v);
59    tree[p].minn=min(tree[p<<1].minn,tree[p<<1|1].minn);
60}
61void read(){
62    scanf("%lld%lld",&n,&lim);
63//    cout << n << "      n     n     "; 
64    for (int i=2;i<=n;i++) scanf("%lld",&d[i]); 
65    for (int i=1;i<=n;i++) scanf("%lld",&c[i]);
66    for (int i=1;i<=n;i++) scanf("%lld",&s[i]);
67    for (int i=1;i<=n;i++) scanf("%lld",&w[i]);
68    s[n+1]=d[n+1]=w[n+1]=1023456789;n++; lim++;
69    for (int i=1;i<=n;i++){
70        l[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d;
71        r[i]=lower_bound(d+1,d+n+1,d[i]+s[i])-d;
72        if (d[r[i]]>d[i]+s[i])
73            r[i]--;
74        addedge(r[i],i);
75    }
76}
77void solve(){
78    int ans=1023456789;
79    for (int i=1;i<=lim;i++){
80        if (i==1){
81            int res=0;
82            for (int j=1;j<=n;j++){
83                dp[j]=res+c[j];
84                for (int k=Head[j];k;k=E[k].nxt)
85                    res+=w[E[k].to];
86            }
87            ans=min(dp[n],ans);
88            continue;
89        }
90        build(1,1,n);
91        for (int j=1;j<=n;j++){
92            if (j!=1)
93                dp[j]=query(1,1,n,1,j-1)+c[j]; else
94                dp[j]=c[j];
95            for (int k=Head[j];k;k=E[k].nxt)
96                if (l[E[k].to]-1>=1)
97                    modify(1,1,n,1,l[E[k].to]-1,w[E[k].to]);//,cout << l[E[k].to]-1 << "  ";
98//        for (int l=1;l<=10;l++) cout <<  tree[l].minn << " ";
99//        cout << "      t    t    ";
100        } 
101    //    cout <<  "     wwwwwww ";
102//        for (int j=1;j<=n;j++) cout << dp[j] << " ";
103//        cout << "   dpdp     dpdpd   "; 
104        ans=min(ans,dp[n]);
105    }
106    cout <<  ans <<  endl;
107}
108
109main(){
110//    freopen("1.in","r",stdin);
111//    freopen("1.out","w",stdout); 
112    read();
113    solve();
114    fclose(stdin);fclose(stdout);
115    return 0;
116}
原文地址:https://www.cnblogs.com/titititing/p/9822560.html