Title Analysis:
First, consider a DP equation, Let f [m] [n] denote that M base stations are currently selected in the first n villages, and the M base station is placed at the minimum value of n. Transfer can enumerate the last base station village, and then calculate the cost between the two villages.
If you think about the cost of a village between two base stations, you’ll find that for a village, it has to pay if and only if the previous base station can’t control it, and the next base station can’t control it, so you can calculate the base station interval that makes it cost-free, and then add impact when it exceeds that interval. specificThat is to add w[i] on line segment tree. Note the scroll array.
Code:
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 }