bzoj 1835 [ZJOI2010]base 基站选址

Posted by

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=1835

题解

设\(f[i][j]\)表示在前\(i\)个村庄建立\(j\)个基站,并保证第\(j\)个基站在第\(i\)个村庄,\(cost[i][j]\)表示在第\(i\)个和\(j\)个村庄建立基站,\(i+1\sim j-1\)村庄的补偿费用;

状态转移方程:

\[f[i][j]=min\{f[k][j-1]+cost[k][i]\}+c[i]\]

首先发现可以优化掉第二维,外层循环枚举\(j\),内层枚举\(i\);

对于第三维枚举\(k\),可以用线段树维护\(min{f[k][j-1]+cost[k][i]}\),当\(i\)增加到\(i+1\)时,\(cost[k][i]\)也会增加,增加的值是原本只被\(i\)覆盖到的村庄的补偿;

于是对于每个村庄求出最左端、最右端可以覆盖到它的村庄的位置,分别记为\(st[i],ed[i]\);

用\(V[i]\)记录\(ed[x]=i\)的村庄\(x\)的集合,当增加\(i\)前,对于每个村庄\(x\),在线段树中\([1,st[x]-1]\)区间(即建设通讯站也不会覆盖\(x\)的部分)加上\(w[x]\);

每次增加\(j\)时重建线段树。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注