题解：P10967 [IOI2000] 邮局（原始版）

· · 题解

DP

题目传送门

解题思路

我们先设 f(i,j) 表示前 i 个村庄放了 j 个邮局的最小距离和。

然后，聪明的你可以很快地想出这个转移方程：

f(i,j) = \min(f(k,j-1)+w(k+1,i))

其中 0<k<i，w(i,j) 表示 i 到 j 的区间内放一个邮局的最小距离之和。

这个转移方程的意思：可以先考虑少放一个邮局的状态，（也就是 f(k,j-1)），然后再加上在 k+1 到 i 这个区间内放一个邮局的距离。

再来讲讲 w(i,j) 怎么算。

首先可以画个图，然后你就会发现：在一个区间内放一个邮局，最优的方案就是放在这个区间中间的村庄（也就是第 \frac{i+j} {2} 个村庄。

可以先不考虑这个区间内的最后一个村庄，那就是 w(i,j-1)。

然后我们再考虑这个区间内的最后一个村庄到邮局的距离，那就是 a_j - a_\frac{(i+j)}{2}。

（其中 a_i 表示第 i 个村庄的位置）

然后将两者相加即可。

最终的式子：

w(i,j)=w(i,j-1)+a_j- a_\frac{(i+j)}{2}

于是，直接 DP 就可以了。

AC 代码

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a[3001];
int f[3001][301];
int w[3001][3001];
//前i个位置，放j个邮局
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            w[i][j]=w[i][j-1]+a[j]-a[(i+j)/2];
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int j=1;j<=m;j++)
    {
        for(int i=j;i<=n;i++)
        {
            for(int k=0;k<i;k++)
            {
                if(f[i][j]>f[k][j-1]+w[k+1][i])
                {
                    f[i][j]=f[k][j-1]+w[k+1][i];
                }
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}