同 zjoi2010 基站选址
- #include<bits/stdc++.h>
- using namespace std;
- #define sight(c) (0<=c&&c<=9)
- #define eho(x) for (int ppp=head[x];ppp;ppp=net[ppp])
- #define v fall[ppp]
- #define N 200007
- #define inf (1<<29)
- int f[N],AAn=inf,n,m,d[N],c[N],r[N],p[N],st[N],ed[N];
- inline void read(int &x){
- static char c;
- for (c=getchar();!sight(c);c=getchar());
- for (x=0;sight(c);c=getchar())x=x*10+c-48;
- }
- void write(int x){if (x<10) {putchar(0+x); return;} write(x/10); putchar(0+x%10);}
- inline void writeln(int x){ if (x<0) putchar(-),x*=-1; write(x); putchar(\n); }
- inline void writel(int x){ if (x<0) putchar(-),x*=-1; write(x); putchar( ); }
- #define Mid (l+r>>1)
- #define ls(x) x<<1,l,Mid
- #define rs(x) x<<1|1,Mid+1,r
- struct suftree{
- int lazy[N<<2],ask[N<<2];
- #define Min(a,b) (a<b?a:b)
- inline void pd(int x) {ask[x]=Min(ask[x<<1],ask[x<<1|1]);}
- inline void down(int x,bool p){
- if (p) return;
- ask[x<<1]+=lazy[x]; ask[x<<1|1]+=lazy[x];
- lazy[x<<1]+=lazy[x]; lazy[x<<1|1]+=lazy[x];
- lazy[x]=0;
- }
- void build(int x,int l,int r){
- lazy[x]=0;
- if (l==r) {ask[x]=f[l];return;}
- build(ls(x)); build(rs(x));
- pd(x);
- }
- void que(int x,int l,int r,int L,int R){
- if (L<=l&&r<=R) {
- AAn=Min(AAn,ask[x]); return;}
- down(x,l==r);
- if (L<=Mid) que(ls(x),L,R);
- if (R> Mid) que(rs(x),L,R);
- }
- void cha(int x,int l,int r,int L,int R,int an){
- if (L<=l&&r<=R) {
- lazy[x]+=an; ask[x]+=an; return;}
- down(x,l==r);
- if (L<=Mid) cha(ls(x),L,R,an);
- if (R> Mid) cha(rs(x),L,R,an);
- pd(x);
- }
- }ST;
- int fall[N<<1],net[N<<1],head[N],tot,re,ans;
- inline void add(int x,int y){
- fall[++tot]=y; net[tot]=head[x]; head[x]=tot;
- }
- signed main () {
- freopen("jhaha.in","r",stdin);
- freopen("jhaha.out","w",stdout);
- read(n); read(m);
- for (int i=2;i<=n;i++) read(d[i]);
- for (int i=1;i<=n;i++) read(c[i]);
- for (int i=1;i<=n;i++) read(r[i]);
- for (int i=1;i<=n;i++) read(p[i]);
- ++n; d[n]=p[n]=inf;
- for (int i=1;i<=n;i++) {
- st[i]=lower_bound(d+1,d+n+1,d[i]-r[i])-d;
- ed[i]=lower_bound(d+1,d+n+1,d[i]+r[i])-d;
- if (d[ed[i]]>d[i]+r[i]) ed[i]--;
- add(ed[i],i);
- }
- for (int i=1;i<=n;i++) {
- f[i]=re+c[i];
- eho(i) re+=p[v];
- } ans=f[n];
- for (int i=1;i<=m;i++) {
- ST.build(1,1,n);
- for (int j=1;j<=n;j++) {
- if (j>i) ST.que(1,1,n,i,j-1);
- f[j]=(j>i?(AAn):0)+c[j];
- eho(j) if (st[v]>1) ST.cha(1,1,n,1,st[v]-1,p[v]);
- AAn=inf;
- }
- ans=min(ans,f[n]);
- }
- writeln(ans); return 0;
- }
来源: http://www.bubuko.com/infodetail-2542070.html