BZOJ1835:基站位置选择问题（动态规划与线段树优化）

dp

F[i][j]=min(F[l][j-1]+w[l][i])+c[i] (w[i][j] l+1 i-1 p d[p]+s[p] d[i] d[p]-s[p] d[l] w[p] )

i+1

w[l][i] d[p]+s[p] d[i]

CODE

#include cstdio

#include iostream

#include cstring

#include algorithm

#include vector

using namespace std;

#define maxn 20100

#define inf 1000000000

struct node {

int l,r,mi,lz;

}t[maxn*8];

#define lc(x) (x 1)

#define rc(x) ((x 1)+1)

#define mi(x) t[x].mi

#define lz(x) t[x].lz

#define mid ((l+r) 1)

#define update(x) mi(x)=min(mi(lc(x)),mi(rc(x)))

int f[maxn],pf[maxn];

int build(int x,int l,int r) {

t[x].l=l,t[x].r=r;

t[x].lz=0;

if (l==r) return t[x].mi=pf[l];

build(lc(x),l,mid);

build(rc(x),mid+1,r);

update(x);

return 0;

}

int pushback(int x) {

if (t[x].l==t[x].r) return 0;

lz(lc(x))+=lz(x),lz(rc(x))+=lz(x);

mi(lc(x))+=lz(x),mi(rc(x))+=lz(x);

lz(x)=0;

}

int query(int x,int x1,int y1){

int l=t[x].l,r=t[x].r;

if (y1 l||x1 r) return inf;

if (x1 =l y1 =r) return mi(x);

pushback(x);

return min(query(lc(x),x1,y1),query(rc(x),x1,y1));

}

int add(int x,int x1,int y1,int z) {

int l=t[x].l,r=t[x].r;

if (y1 l||x1 r) return 0;

if (x1 =l y1 =r) return lz(x)+=z,mi(x)+=z;

pushback(x);

add(lc(x),x1,y1,z),add(rc(x),x1,y1,z);

update(x);

}

int n,k;

int c[maxn],s[maxn],d[maxn],w[maxn];

int st[maxn],ed[maxn];

vector int list[maxn];

int solve(){

int sum=0;

for (int i=1;i i++) {

f[i]=sum+c[i];

for(int j=0;j list[i].size();j++) sum+=w[list[i][j]];

}

int ans=f[n];

for (int i=1;i i++) {

//for (int i=1;i i++) printf( %d ,f[i]);printf( \n

memcpy(pf,f,sizeof(pf));

for (int j=1;j j++) f[j]=inf;

build(1,1,n);

for (int j=1;j j++){

f[j]=min(f[j],query(1,1,j-1))+c[j];

for (int k=0;k list[j].size();k++) add(1,1,st[list[j][k]]-1,w[list[j][k]]);

}

ans=min(ans,f[n]);

}

printf( %d\n ,ans);

return 0;

}

int main(){

scanf( %d%d , n,

for (int i=2;i i++) scanf( %d ,d+i);

for (int i=1;i i++) scanf( %d ,c+i);

for (int i=1;i i++) scanf( %d ,s+i);

for (int i=1;i i++) scanf( %d ,w+i);

d[++n]=inf,c[n]=w[n]=s[n]=0;

for (int i=1;i i++) {

st[i]=lower_bound(d+1,d+1+n,d[i]-s[i])-d;

ed[i]=upper_bound(d+1,d+1+n,d[i]+s[i])-d-1;

list[ed[i]].push_back(i);

}

solve();

return 0;

}