BZOJ1835 [ZJOI2010] 基站选址【动态规划】【线段树】

约定不等于承诺〃 2021-09-30 03:16 248阅读 0赞

题目分析：

首先想一个DP方程，令f\[m\]\[n\]表示当前在前n个村庄选了m个基站，且第m个基站放在n处的最小值，转移可以枚举上一个放基站的村庄，然后计算两个村庄之间的代价。

仔细思考两个基站之间村庄的代价，会发现对于一个村庄，它需要付出代价的时候当且仅当上一个基站控制不到它，下一个基站也控制不到它，所以可以计算使它不付出代价的基站区间，然后在超过这段区间的时候加影响。具体来说就是在线段树上面加w\[i\]。注意滚动数组。

代码：

1 #include<bits/stdc++.h>
      2 using namespace std;
      3 
      4 const int maxn = 25000;
      5 const int inf = 2000000000;
      6 
      7 int n,k;
      8 int d[maxn],c[maxn],s[maxn],w[maxn];
      9 int l[maxn],r[maxn];
     10 
     11 int Minn[2][20100<<2],lazy[2][20100<<2];
     12 
     13 void read(){
     14     scanf("%d%d",&n,&k);
     15     for(int i=2;i<=n;i++) scanf("%d",&d[i]);
     16     for(int i=1;i<=n;i++) scanf("%d",&c[i]);
     17     for(int i=1;i<=n;i++) scanf("%d",&s[i]);
     18     for(int i=1;i<=n;i++) scanf("%d",&w[i]);
     19 }
     20 
     21 void push_down(int dd,int now){
     22     if(Minn[dd][now<<1] != inf){
     23     Minn[dd][now<<1] += lazy[dd][now];
     24     lazy[dd][now<<1] += lazy[dd][now];
     25     }
     26     if(Minn[dd][now<<1|1] != inf){
     27     Minn[dd][now<<1|1] += lazy[dd][now];
     28     lazy[dd][now<<1|1] += lazy[dd][now];
     29     }
     30     lazy[dd][now] = 0;
     31 }
     32 
     33 void push_up(int dd,int now){
     34     Minn[dd][now] = min(Minn[dd][now<<1],Minn[dd][now<<1|1]);
     35 }
     36 
     37 void Modify(int dd,int now,int tl,int tr,int l,int r,int dt){
     38     if(Minn[dd][now] == inf) return;
     39     if(tl >= l && tr <= r){Minn[dd][now]+=dt; lazy[dd][now]+=dt;return;}
     40     if(tl > r || tr < l){
        return;}
     41     if(lazy[dd][now]) push_down(dd,now);
     42     int mid = (tl+tr)/2;
     43     Modify(dd,now<<1,tl,mid,l,r,dt);
     44     Modify(dd,now<<1|1,mid+1,tr,l,r,dt);
     45     push_up(dd,now);
     46 }
     47 
     48 int Query(int dd,int now,int tl,int tr,int l,int r){
     49     if(tl >= l && tr <= r){
        return Minn[dd][now];}
     50     if(tl > r || tr < l){
        return inf;}
     51     if(lazy[dd][now]) push_down(dd,now);
     52     int mid = (tl+tr)/2;
     53     int ans=min(Query(dd,now<<1,tl,mid,l,r),Query(dd,now<<1|1,mid+1,tr,l,r));
     54     push_up(dd,now);
     55     return ans;
     56 }
     57 
     58 vector <int> g[maxn];
     59 void init(){
     60     for(int i=1;i<=n;i++){
     61     int lft = 1,rgt = i;
     62     while(lft < rgt){
     63         int mid = (lft+rgt)/2;
     64         if(d[i]-d[mid] > s[i]) lft = mid+1; else rgt = mid;
     65     }
     66     l[i] = lft; lft = i,rgt = n;
     67     while(lft < rgt){
     68         int mid = (lft+rgt+1)/2;
     69         if(d[mid]-d[i] > s[i]) rgt = mid-1; else lft = mid;
     70     }
     71     r[i] = lft;
     72     }
     73     for(int i=1;i<=n;i++){g[r[i]+1].push_back(i);}
     74 }
     75 
     76 void work(){
     77     init(); n++;int ans=0;
     78     for(int i=1;i<=n;i++){ans += w[i]; Modify(0,1,1,n,i,i,inf);}
     79     for(int j=1,od=1;j<=k+1;j++,od^=1){
     80     memset(Minn[od],0,sizeof(Minn[od]));
     81     memset(lazy[od],0,sizeof(lazy[od]));
     82     int z = c[j];
     83     for(int i=1;i<j;i++) z+=c[i],Modify(od,1,1,n,i,i,inf);
     84     Modify(od,1,1,n,j,j,z);
     85     int pp = 0;
     86     for(int i=1;i<=n;i++){
     87         for(int st=0;st<g[i].size();st++){
     88         Modify(od^1,1,1,n,1,l[g[i][st]]-1,w[g[i][st]]);
     89         pp += w[g[i][st]];
     90         }
     91         if(i <= j) continue;
     92         Modify(od,1,1,n,i,i,min(Query(od^1,1,1,n,1,i-1),pp)+c[i]);
     93     }
     94     ans = min(ans,Query(od,1,1,n,n,n));
     95     }    
     96     printf("%d",ans);
     97 }
     98 
     99 int main(){
    100     read();
    101     work();
    102     return 0;
    103 }

转载于:https://www.cnblogs.com/Menhera/p/9563897.html