menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[wqs二分+DP]POJ1160【Post Office】题解
apps POJ
local_offer 查看标签
comment 0 条评论

题目概述

有 $n$ 个村庄,现在要建 $m$ 个邮局,一种方案的代价是每个村庄到最近的邮局的距离之和。

解题报告

显然是 $O(n^2m)$ DP吧?数据小的可怜,这样就可以过了……

不过有一种更好的方法,可以把 $m$ 优化到 $log_2m​$ ,这就是wqs(%%%Orz)二分了。

想法是这样的:去掉 $f[i][j]$ (前 $i$ 个村庄中建了 $j$ 个邮局)中的 $j$ ,枚举一个 $cost$ 表示建邮局需要额外的 $cost$ 花费,再记录一个 $g[i]$ 表示前 $i$ 个村庄在最优解的情况下最少建多少邮局。接下来刷DP,如果 $g[n]\le m$ 就说明可行。由此可见 $cost$ 是可以二分枚举的,所以我们就可以愉快的把 $O(n^2m)$ 优化成 $O(n^2log_2m)$ 。

严格的来说,只有当原函数 $g(x)$ 的斜率单调,才可以这么处理。因为枚举 $cost$ 实际上是一个逼近 $g(x)$ 斜率的过程 $[g(x)-x\cdot cost]'=g'(x)-cost$ ,如果 $g'(x)$ 不是单调的,就没办法二分枚举 $cost$ 了。

还有要注意的是,最后并不一定刚好停在 $m$ 个的位置,因为最优答案可能有一段相同。所以算答案的时候不能用 $f[n]-g[n]\cdot cost$ ,一定要用 $f[n]-m\cdot cost$ 。

另一道经典的wqs二分是BZOJ2654,那时候说这二分怎么这么神奇,原来是wqs二分QAQ。

解题报告

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=300;

int n,m,dis[maxn+5],pre[maxn+5][maxn+5],suf[maxn+5][maxn+5],w[maxn+5][maxn+5];
int f[maxn+5],g[maxn+5];

inline void Fix(int fj,int gj,int &fi,int &gi) {if (fj<fi||fj==fi&&gj<gi) fi=fj,gi=gj;}
inline bool check(int cst){
    memset(f,63,sizeof(f));f[0]=0;g[0]=0;
    for (int i=1;i<=n;i++)
        for (int j=0;j<i;j++)
            Fix(f[j]+w[j+1][i]+cst,g[j]+1,f[i],g[i]);
    return g[n]<=m;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&dis[i]);
    for (int i=1;i<=n;i++) for (int j=i;j;j--) pre[j][i]=pre[j+1][i]+dis[i]-dis[j];
    for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) suf[i][j]=suf[i][j-1]+dis[j]-dis[i];
    for (int i=1,k;i<=n;i++)
        for (int j=(k=i);j<=n;j++)
            w[i][j]=pre[i][i+j>>1]+suf[i+j>>1][j];
    int L=0,R=dis[n]*n;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) check(mid)?R=mid-1:L=mid+1;
    return check(L),printf("%d\n",f[n]-m*L),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up