题解：P2803 学校选址 II

· · 题解

题目传送门

思路

可以发现，这一题 n,k \le 100，是完全可以用 O(n^3) 的，优先考虑动态规划。

可以发现这题中只有 n,k，所以可以定义 dp_{i,j} 表示对前 j 栋楼来说，建造 i 所学校学生所走的距离和的最小值。

定义 f_{i,j} 表示在 i 到 j 号楼之间，安置一所学校学生所走的距离和的最小值。那么就可以得出：

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

那么怎么求 f 数组呢？可以发现假设这 n 栋楼分别有 x_1,x_2,x_3,\cdots,x_n 个学生，那么最短距离就是：

\sum_{i=1}^{n}x_i \cdot dis_{i,k}

那么为了使得距离和最小，所以 x_i 应该平均分配，所以使得

\sum_{i=1}^{k} x_i \text{ 与} \sum_{i=k+1}^{n} x_i \text{ 的差最小}

找到这个 k 之后，就可以将 f 数组求出来了。

有了 f 数组后，我们就可以求出 dp 数组了。

代码

#include<bits/stdc++.h>
using namespace std;
int a[120],b[120];
int s1[120][120],s2[120][120];//s1[i][j]表示i到j的学生人数，s2[i][j]表示i到j的距离
long long f[120][120];\\f[i][j]表示在i到j之间安置一所学校学生所走的距离和的最小值
long long dp[120][120];\\dp[i][j]表示对前j栋楼来说，建造i所学校学生所走的距离和的最小值
int main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=2;i<=n;i++) cin>>b[i];
    for (int i=1;i<=n;i++)//计算学生人数区间
    {
        for (int j=i;j<=n;j++)
        {
            s1[i][j]=s1[i][j-1]+a[j];
        }
    }
    for (int i=1;i<=n;i++)//计算距离
    {
        for (int j=i+1;j<=n;j++)
        {
            s2[i][j]=s2[i][j-1]+b[j];
        }
    }
    memset(dp,0x3f,sizeof(dp));//赋极大值（用于找极小值）
    memset(f,0,sizeof(f));//清空
    for (int i=1;i<=n;i++)
    {
        for (int j=i;j<=n;j++)
        {
            for (int l=i;l<=j;l++)
            {
                if (s1[i][l]<s1[l+1][j]) continue;//找两边学生人数差最小的中点
                for (int k=i;k<=l;k++) f[i][j]+=a[k]*s2[k][l];
                for (int k=l+1;k<=j;k++) f[i][j]+=a[k]*s2[l][k];
//计算最短距离
                break;
            }
        }
    }
    for (int i=1;i<=n;i++) dp[1][i]=f[1][i];//初始化
    for (int i=2;i<=m;i++)
    {
        for (int j=i;j<=n;j++)
        {
            for (int l=i-1;l<=j-1;l++)
            {
                dp[i][j]=min(dp[i][j],dp[i-1][l]+f[l+1][j]);//状态转移方程
            }
        }
    }
    cout<<dp[m][n];//输出
}