描述高速公路旁有一定数量的村庄。高速公路可被视为一整数轴村庄位置与整数坐标对应。没有两个村庄在同一坐标上两村庄的距离为坐标差的绝对值。现将邮局建在村庄上即表示邮局与村庄有相同的位置。构建过程中邮局的位置应使得所有村庄与其最近邮局的距离之和最小。编写一程序用给定位置的村庄和邮局数量计算出村庄与其最近邮局的距离和的最小值。输入描述程序从标准输入读取。第一行包含一个整数tcase表示测试组数。每组输入数

#include #include #include #include using namespace std;

int main() { int tcase; cin >> tcase;

while (tcase--) {
    int V, P;
    cin >> V >> P;
    
    vector<int> positions(V);
    for (int i = 0; i < V; ++i) {
        cin >> positions[i];
    }
    
    sort(positions.begin(), positions.end());
    
    vector<vector<int>> dp(V + 1, vector<int>(P + 1, INT_MAX));
    vector<vector<int>> cost(V + 1, vector<int>(V + 1, 0));
    
    for (int i = 1; i <= V; ++i) {
        for (int j = i; j <= V; ++j) {
            int mid = (i + j) / 2;
            for (int k = i; k <= j; ++k) {
                cost[i][j] += abs(positions[k - 1] - positions[mid - 1]);
            }
        }
    }
    
    for (int i = 1; i <= V; ++i) {
        dp[i][1] = cost[1][i];
    }
    
    for (int i = 2; i <= V; ++i) {
        for (int j = 2; j <= min(i, P); ++j) {
            for (int k = i - 1; k >= j - 1; --k) {
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + cost[k + 1][i]);
            }
        }
    }
    
    cout << dp[V][P] << endl;
}

return 0;

}