IOI2000 Post Office

wjh15101051's space

卧薪尝胆，厚积薄发。

IOI2000 Post Office

Date: Fri Aug 10 22:38:04 CST 2018

In Category: NoCategory

Description：

有 $n$ 个村庄，第 $i$ 个在 $p_i$ ，在其中 $m$ 个建邮局，问每个村庄走到离其最近的邮局的距离和的最小值。

$k\le n \le 300$

Solution：

设 $w(i,j)$ 为 $[i,j]$ 内建一个邮局 $[i,j]$ 都走到这个邮局的最小代价，发现应该建在中位数即 $p_{\frac {i+j+1}2}$ 上。

有 $\begin{align}w(i,j)=\sum_{k=i}^j |p_k-p_{\frac {i+j+1}2}|=-\sum_{k=i}^{\lfloor\frac {i+j-1}2\rfloor}p_k+\sum_{k=\lfloor\frac {i+j+1}2\rfloor+1}^jp_k\end{align}$

$w(i,j)=w(i,j-1)+p_j-p_{\lfloor\frac{i+j}2\rfloor}$

$w(i,j)=w(i+1,j)-p_i+p_{\lfloor\frac{i+j}2\rfloor}$

$f[i][j]=min{f[i-1][k]+w(k+1,j)}$

发现是经典的 $1D/1D$ 动态规划，只要证明 $w$ 满足四边形不等式和区间包含性即可证明 $f$ 满足决策单调性。

区间包含性显然。

$$w(i,j)+w(i+1,j+1)\le w(i,j+1) + w(i+1,j)$ $

$$2w(i,j)+p_i-p_{\lfloor\frac{i+j}2\rfloor}+p_{j+1}-p_{\lfloor\frac{i+j+2}2\rfloor}\le 2w(i,j)+p_{j+1}-p_{\lfloor\frac {i+j+1}2\rfloor}+p_i-p_{\frac {i+j} 2}$ $

$$-p_{\frac{i+j+2}2}\le-p_{\frac {i+j+1}2}$ $

显然成立。

则 $f$ 满足四边形不等式，且满足 $f[i][i]=0$ ，满足决策单调性。于是 $f[i][j]$ 只用从 $[s[i][j-1],s[i+1][j]]$ 转移即可。

长得和区间 $DP$ 一模一样。

不是很理解。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 310

int p[MAXN];

int w[MAXN][MAXN];

int f[MAXN][MAXN];

int s[MAXN][MAXN];

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;++i)scanf("%d",&p[i]);

    memset(f,0x3f,sizeof(f));

    for(int i = 1;i <= n;++i)

    {

    	w[i][i] = 0;

		for(int j = i + 1;j <= n;++j)

		{

			w[i][j] = w[i][j - 1] + p[j] - p[(i + j) / 2];

		}

	}

    for(int i = 0;i <= n;++i)

    {

        f[i][i] = 0;

        s[i][i] = i;

    }

    for(int l = 2;l <= n - m + 1;++l)

    {

        for(int i = 1;i <= n - l + 1;++i)

        {

            int j = i + l - 1;

            for(int k = s[i][j - 1];k <= s[i + 1][j];++k)

            {

                if(f[i][j] > f[i - 1][k - 1] + w[k][j])

                {

                    f[i][j] = f[i - 1][k - 1] + w[k][j];

                    s[i][j] = k;

                }

            }

        }

    }

    cout << f[m][n] << endl;

    return 0;

}

In tag: DP-四边形不等式优化区间DP

wjh15101051