P4767 [IOI2000]邮局题解

· · 题解

题意：

题很简单，大意是给你 n 个村庄的坐标（就一个数字），让你盖 p 个邮局，问你怎么盖能让所有村庄到邮局的距离之和最小。

思路:

首先显然动态规划嘛O(∩_∩)O

数组 f_{i,j}=i 个村庄时盖 j 个镖局的答案。

【再建一个数组 min （写代码的时候当然不能用这个名字）， min_{i,j}=i 到 j 这几个村庄如果只设一个镖局的答案，很显然应该放在中心，也就是 (i+j)\div2 这里。】

---------状态转移方程分割线---------

  1. f_{i,j}=\min{f_{k,j-1}+min_{k+1,j}}

很显然不用过多解释了吧（假的。

首先， j 个镖局最少要有 j 个村庄 (这不是废话吗)。

好，那么接下来，i个村庄j个镖局如果再加上 x 个村庄这种方法是被允许的。

于是，k 的范围应该在 j-1 到 i 之间。

  1. min_{i,j}=min_{i,j-1}+location_{j}-location_{(i+j)\div2}
这也不多说了，刚才说过了（详见用【】框起来的部分）

-----------50分代码-----------

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n , p , d[3005] , f[3005][305] , m[3005][3005];
int main(){
    scanf ("%d%d" , &n , &p);
    for(int i = 0; i < n; i ++)scanf ("%d" , &d[i]);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j <= min(i , p - 1); j ++)
            f[i][j] = 0x3f3f3f3f;
    for(int i = 0; i < n; i ++){
        for(int j = i + 1; j < n; j ++)
            m[i][j] = m[i][j - 1] + d[j] - d[i + j >> 1];   
        f[i][0] = m[0][i];
    }
    for(int i = 1; i < n; i ++)
        for(int j = 1; j <= min(i , p - 1); j ++)
            for(int k = j - 1; k < i; k ++)
                f[i][j] = min(f[i][j] , f[k][j - 1] + m[k + 1][i]);
    printf ("%d" , f[n - 1][p - 1]);
    return 0;
}

但是这个程序的运算次数为 30\times300\times300=27\times10^8=2.7\times10^9，而现在一秒最多只能跑 10^8 次，所以只能得 50 分。

但我们发现放邮局的地方是具有单调性的，因为如果放的再靠前的话他也不如放在后面好，所以我们可以用一个数组 P_{i,j} 来记录，它代表前 i 个村庄放第 j 个邮局的地方，每次从 P_{i,j-1} 开始枚举，因为他是有单调性的，所以可以从 P_{i,j-1} 开始。

把这个加上的话，就可以去掉一些重复部分，所以可以过。

-----------AC 代码-----------

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f , N = 3010 , M = 310;
int n , p;
int d[N];
int f[N][M] , g[N][N] , P[N][N];
int i , j , k;
int main(){
    scanf ("%d%d" , &n , &p);
    for(i = 0; i < n; ++ i)scanf ("%d" , &d[i]);
    for(i = 0; i < n; ++ i)
        for(j = 0; j <= min(i , p - 1); j ++)
            f[i][j] = INF;
    for(i = 0; i < n; ++ i){
        for(j = i + 1; j < n; ++ j)
            g[i][j] = g[i][j - 1] + d[j] - d[(i + j) / 2];  
        f[i][0] = g[0][i];
    }
    for(i = 1; i < n; ++ i)
        for(j = 1; j <= min(i , p - 1); ++ j) {
            for(k = P[i][j - 1]; k < i; ++ k) 
                if (f[i][j] > f[k][j - 1] + g[k + 1][i]) {
                    f[i][j] = f[k][j - 1] + g[k + 1][i];
                    P[i][j] = k;
                }
        }
    printf ("%d" , f[n - 1][p - 1]);
    return 0;
}