[ZJOI2010 base 基站选址]线段树优化的动态规划★★

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1835
【算法分析】
首先第一直觉就能写出一个状态和方程。
F[i][j]表示第i个地点建站，然后前i个村庄一共建了j个站时的前i个村庄需要的最小费用。
于是顺理成章的方程：
F[i][j]=min(F[l][j-1]+w[l][i])+c[i]
其中w[l][i]是这样定义的：
    从l+1到i-1这些点p里，所有满足d[p]+s[p]当然，这还是其次，最重要的是我们可能可以对每一层建立一个数据结构降低转移的复杂度。

让我们来观察假设i+1以后，方程里的东西有什么变化。

F[l][j-1]和c[i]显然不变。那么变得只是w[l][i]。
他怎么变呢？
围观一下上面红色的w[l][i]的定义，容易发现，唯一边的就是：
d[p]+s[p]而与它的w有关的转移范围显然是所有满足d[j]（具体求那个范围可以在一开始就二分出来。然后用一个邻接表起结束位置的点）
【时间复杂度】O(nk lg n)
【其它】2Y。第一次错是因为看错了一点题目，题目要求是<=k个站，而不是必须建k个站。。。
ZJOI2010 Day1 Finished。
【CODE】
#include #include #include const int N=25555;
const int INF=1000000005;
int n,k;
int pF[N],F[N],c[N],d[N],s[N],w[N],st[N],ed[N];
inline int min(int x,int y){return xstruct Segment_Type{
struct Node{int l,r,key,delta;}Tr[N*6];

void pushdown(int p){
if (!Tr[p].delta) return;
if (Tr[p].l!=Tr[p].r){
Tr[p<<1].delta+=Tr[p].delta;
Tr[(p<<1)+1].delta+=Tr[p].delta;
}
Tr[p].key+=Tr[p].delta;
Tr[p].delta=0;
}

void update(int p){
pushdown(p<<1);
pushdown((p<<1)^1);
Tr[p].key=min(Tr[p<<1].key,Tr[(p<<1)^1].key);
}

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r; Tr[p].delta=0;
if (l==r){
Tr[p].key=pF[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build((p<<1)^1,mid+1,r);
update(p);
}

void add(int p,int l,int r,const int delta){
if (l>r) return;
if (l<=Tr[p].l && Tr[p].r<=r)
Tr[p].delta+=delta;
else{
pushdown(p);
int mid=(Tr[p].l+Tr[p].r) >> 1;
if (l<=mid) add(p<<1,l,r,delta);
if (r> mid) add((p<<1)^1,l,r,delta);
update(p);
}
}

int solve(int p,int l,int r){
if (l>r || r pushdown(p);
if (l<=Tr[p].l && Tr[p].r<=r) return Tr[p].key;
return min(solve(p<<1,l,r),solve((p<<1)^1,l,r));
}
}Segment_Tree;

struct edge{int x,y;edge *next;};
struct Lint_t{
edge g[N],*ls[N];
int e;
void init(){e=0;memset(ls,0,sizeof(ls));}
void add(int x,int y){g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];}
}Ed_Link;

int Findl(int x){
int l=1,r=n,mid;
while (l mid=(l+r)>>1;
if (x<=d[mid]) r=mid;
else l=mid+1;
}
return l;
}

int Findr(int x){
int l=1,r=n,mid;
while (l+1 mid=(l+r)>>1;
if (d[mid]<=x) l=mid;
else r=mid-1;
}
if (d[r]<=x) l=r;
return l;
}

void input(){
scanf("%d%d",&n,&k);
int i;
for (i=2;i<=n;i++) scanf("%d",&d[i]);
for (i=1;i<=n;i++) scanf("%d",&c[i]);
for (i=1;i<=n;i++) scanf("%d",&s[i]);
for (i=1;i<=n;i++) scanf("%d",&w[i]);
d[n+1]=d[n]+INF; c[n+1]=w[n+1]=s[i]=0;
n++;
Ed_Link.init();
for (i=1;i<=n;i++){
st[i]=Findl(d[i]-s[i]);
ed[i]=Findr(d[i]+s[i]);
Ed_Link.add(ed[i],i);
}
}

void dp(){
if (k==0){
int Sum=0;
for (int i=1;i<=n;i++) Sum+=w[i];
printf("%dn",Sum);
return;
}
int i,j,Sum=0,ans=INF;
for (i=1;i<=n;i++){
F[i]=Sum+c[i];
for (edge *t=Ed_Link.ls[i];t;t=t->next)
Sum+=w[t->y];
}
for (j=1;j<=k;j++){
ans=min(ans,F[n]);
memcpy(pF,F,sizeof(F));
for (i=1;i<=n;i++) F[i]=INF;
Segment_Tree.build(1,1,n);
for (i=1;i<=n;i++){
F[i]=min(F[i],Segment_Tree.solve(1,1,i-1)+c[i]);
for (edge *t=Ed_Link.ls[i];t;t=t->next)
Segment_Tree.add(1,1,st[t->y]-1,w[t->y]);
}
}
ans=min(ans,F[n]);
printf("%dn",ans);
}

int main(){
input();
dp();
}