自动搬运

查看原文

来自洛谷，原作者为

	edward1346 这个家伙很CAI，什么都留下了

搬运于2025-08-24 23:03:01，当前版本为作者最后更新于2024-09-08 15:56:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}