题解 P4677 【山区建小学】

· · 题解

这明显是一道DP题。通过观察n，m的范围（500）可得，题目要求在O(n^3)的时间复杂度内完成状态转移。

我们设计dp[i][j]表示在前i个村庄中建立j个小学的最小距离总和。设f[i][j]表示在村庄区间[i,j]中（从第i个村庄到第j个村庄，包括两边）只建1座小学的最小距离总和。那么我们可以得到状态转移方程：

dp[i][j]=min\{dp[k][j-1]+f[k+1][i]\}

这样我们计算出f数组，就可以在O(n^2\times m)的时间复杂度内完成状态转移了。

那么问题来了：怎样计算f[i][j]呢？

（这里需要一点直觉）在区间[i,j]内建一所小学，当然是要建在正中间，这样可以保证方案最优。所以，我们只需要选择区间的中点，即编号为mid=\frac{i+j}2的点，然后计算出所有村庄到该点的距离，即

f[i][j]=\sum_{k=i}^j |distance(k,mid)|~~~(mid=\frac{i+j}2)

f[i][j]$的计算的时间复杂度为$O(n^3)

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510;
const int inf=2e9;
int n,m,a[maxn],f[maxn][maxn],dp[maxn][maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)scanf("%d",a+i),a[i]+=a[i-1];
    for(int l=1;l<=n;l++)for(int r=l;r<=n;r++)
    {
        int mid=(l+r)>>1;
        for(int k=l;k<=r;k++)f[l][r]+=abs(a[mid]-a[k]);
    }
    for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)dp[i][j]=inf;
    dp[0][0]=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
    {
        if(j>i){dp[i][j]=0;continue;}
        for(int k=j-1;k<=i;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+f[k+1][i]);
    }
    printf("%d\n",dp[n][m]);
    return 0;
}