[ZJOI2011]基站选址
【题目分析】
一条直线上给定相对距离Di（距第一个村庄的距离）的N个村庄中建K个基站，每个村庄i接收的范围为前后Si，建基站费用Ci，一个村庄要么被接受到要么额外支付Wi。设计方案求最小总费用。
【算法分析】
朴素方程为f[i][j](前i个村庄中选j个基站，第j个建在i)=MIN(f[k][j-1]+W[k+1..j](表示k+1..j村庄中建一个基站后覆盖所有k+1..j（没覆盖就支付费用）所需的最小总和)).W预处理需要N^3时间，DP需要N^2*K的时间。显然需要优化。
其实这样一个“裸”的方程看起来似乎很难再在时间上优化下去，因为该算法的瓶颈在于预处理的“复杂”（预处理涉及到题中的C、S、W）。这时，我们就需要对方程进行改变，让其显得更加“简洁”。f[i][j](前i个村庄中选j个基站，第j个建在i)=MIN(f[k][j-1]+W[k+1..j]（k+1..j中k和i都覆盖不到的村庄的W和）+Ci。Ci为常数，DP又可以滚动优化，所以方程实际上要干的事就是f[i]=MIN(f[k]+W[k+1..j])。为了计算方便，我们可以再在最后面设一个村庄n+1，k增加1，令d[n+1]=INF。那么基站数量一定下，最优解就是f[n]。
显然现在我们对于每个村庄，都可以在O(logn)的时间内二分查找出它向前向后最多能覆盖到的地方，这个预处理在后面的分析中会用到。
我们进一步分析W[k+1..j]的计算。显然一个村庄p覆盖不到的条件是同时满足Dp+Sp<Di,Dp-Sp>Dk.现在我们假设有一个k，一个i，考虑覆盖到的村庄。
我们现在假设k不变，i增大1，那么会发生什么变化？很显然，原本被k覆盖到的村庄还是被覆盖的，但被i覆盖到的村庄左边一部分没有被覆盖了，也就意味着这些村庄需要另外给付钱了！回到那个条件，我们发现这便是Di单调递增使得一些原本覆盖到的村庄p覆盖不到了！如果我们已知W[k+1..i]，怎么求出W[k+1..i+1]？很显然的，加上新增的村庄的W即可。
当然，事情还没那么简单，由于我们DP时是固定i求一个k使解最小，自然而然我们可以初步想到一个思路用线段树维护每个f[k]+W[k+1..j]的值，“新增的村庄”打个标记加上去就行。
算法流程：
读入，预处理每个村庄向前向后最多能覆盖到的地方记为st[i],ed[i]
循环j=1..k表示当前建第几个村庄
利用上次的f（即每个点的初值）建线段树
清空旧的f
循环i=1..n
查找线段树中0..i-1里f的最小值
最小值+Ci后赋值给f[i]
对于i，若ed[x]=i，则在线段树中0..st[x]-1集体加上Wx
(原因：考虑每个x（满足ed[x]=i，具体实现可用链表（数组模拟）），这样做是为 了对于i后面的村庄如果选定村庄k，且x够不到（x原本刚刚好能被i覆盖）， 那么这个k的f[k]就要加上Wx了。）
用当前的f[n]更新最优解
输出最优解
时间复杂度O(knlogn)
空间复杂度O(n)
【总结】
DP优化，突破口就是利用了Di单调递增的性质，并合理使用数据结构加以优化。
【吐槽】
算法分析第二段及之后均为看题解后总结得来。
【附程序】
- #include<cstdio>
- #include<cstring>
- #define rep(i,x,y) for(i=x;i<=y;i++)
- #define rep_(i,x,y) for(i=x;i>=y;i--)
- #define MIN(x,y) ((x)<(y)?(x):(y))
- #define MAX(x,y) ((x)>(y)?(x):(y))
- using namespace std;
- const int INF=~0U>>2;
- const int MAXN=20010;
- const int MAXK=102;
- typedef int arr[MAXN];
- int n,k,i,j,pos,ans,min0,en0;
- arr d,c,s,w,f,st,ed;
- struct tree
- {
- int min[1<<16],en[1<<16];
- void pdown(int i)
- {
- en[i<<1]+=en[i];min[i<<1]+=en[i];
- en[(i<<1)+1]+=en[i];min[(i<<1)+1]+=en[i];
- en[i]=0;
- }
- void pup(int i)
- {
- min[i]=MIN(min[i<<1],min[(i<<1)+1]);
- }
- void build(int i,int x,int y)
- {
- en[i]=0;
- if(x!=y)
- {
- build(i<<1,x,(x+y)>>1);
- build((i<<1)+1,((x+y)>>1)+1,y);
- pup(i);
- }
- else min[i]=f[x];
- }
- void find(int i,int x,int y,int l,int r,int kind)
- {
- if(x>y)return;
- if(l>y || r<x)return;
- if(x>=l && y<=r)
- {
- switch(kind)
- {
- case 1: //查找最小值
- min0=MIN(min0,min[i]);
- break;
- case 2: //加上一个值
- en[i]+=en0;min[i]+=en0;
- break;
- }
- }
- else
- {
- pdown(i);
- find(i<<1,x,(x+y)>>1,l,r,kind);
- find((i<<1)+1,((x+y)>>1)+1,y,l,r,kind);
- pup(i);
- }
- }
- }a;
- struct biao
- {
- int edge;
- arr e,b,first,last,w;
- void clean()
- {
- edge=0;
- memset(first,-1,sizeof(first));
- memset(b,-1,sizeof(b));
- }
- void add(int x,int y,int z)
- {
- e[edge]=y;w[edge]=z;
- if(first[x]==-1)first[x]=edge;
- else b[last[x]]=edge;
- last[x]=edge++;
- }
- }q;
- int findl(int x)
- {
- int l,r;
- for(l=1,r=n;l<r;)
- {
- if(x<=d[(l+r)>>1])r=(l+r)>>1;
- else l=((l+r)>>1)+1;
- }
- return l;
- }
- int findr(int x)
- {
- int l,r;
- for(l=1,r=n;l<r;)
- {
- if(x>=d[(l+r+1)>>1])l=(l+r+1)>>1;
- else r=((l+r+1)>>1)-1;
- }
- return l;
- }
- int main()
- {
- freopen("base.in","r",stdin);
- freopen("base.out","w",stdout);
- scanf("%d%d",&n,&k);
- rep(i,2,n)scanf("%d",&d[i]);
- rep(i,1,n)scanf("%d",&c[i]);
- rep(i,1,n)scanf("%d",&s[i]);
- rep(i,1,n)scanf("%d",&w[i]);
- n++;d[n]=INF;k++;
- q.clean();
- rep(i,1,n)
- {
- st[i]=findl(d[i]-s[i]);
- ed[i]=findr(d[i]+s[i]);
- q.add(ed[i],st[i]-1,w[i]);
- }
- ans=INF;
- f[0]=0;rep(i,1,n)f[i]=INF;
- rep(j,1,k)
- {
- a.build(1,0,n);
- f[0]=0;rep(i,1,n)f[i]=INF;
- rep(i,1,n)
- {
- min0=INF;
- a.find(1,0,n,0,i-1,1);
- f[i]=min0+c[i];
- for(int pos=q.first[i];pos>=0;pos=q.b[pos])
- {
- en0=q.w[pos];
- a.find(1,0,n,0,q.e[pos],2);
- }
- }
- ans=MIN(ans,f[n]);
- }
- printf("%d\n",ans);
- scanf("\n");
- return 0;
- }