一本通-1197：山区建小学（区间DP）

【题目描述】 政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数)，其中，0<i<m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学(设0<n≤m<500)。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

【输入】 第1行为m和n，其间用空格间隔

2行为m−1个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。

例如:

10 3

2 4 6 5 2 4 3 1 3

表示在10个村庄建3所学校。第1个村庄与第2个村庄距离为2，第2个村庄与第3个村庄距离为4，第3个村庄与第4个村庄距离为6，...，第9个村庄到第10个村庄的距离为3。

【输出】 各村庄到最近学校的距离之和的最小值。

【输入样例】 10 2 3 1 3 1 1 1 1 1 3

【输出样例】 18

---

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

int school, n;
//dp[i][j]表示前i个村庄建立j个学校的最小和
//m[i][j]表示第i个村庄到第j个村庄只建立一所学校的最小和
vector<vector<int> > d(505, vector<int>(505, INT_MAX / 2)), m(505, vector<int>(505));
vector<int> pos(505); //每个村庄的绝对坐标

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> school;
    for (int i = 2; i <= n; ++i) {
        int dis; cin >> dis;
        pos[i] = pos[i - 1] + dis;
    }

    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            m[i][j] = m[i][j - 1] + pos[j] - pos[(i + j) >> 1];
        }
    }

    for (int i = 1; i <= n; ++i) d[i][1] = m[1][i];

    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j <= i && j <= school; ++j) {
            for (int k = j - 1; k < i; ++k) {
                d[i][j] = min(d[i][j], d[k][j - 1] + m[k + 1][i]);
            }
        }
    }
    cout << d[n][school] << endl;

    return 0;
}

这道题目注意输入的是各个村庄之间的距离，需要转化一步算出绝对的坐标。

//dp[i][j]表示前i个村庄建立j个学校的最小和
//m[i][j]表示第i个村庄到第j个村庄只建立一所学校的最小和
//pos[i]表示第i个村庄的绝对坐标，第一个村庄在位置0
//村庄从1开始计数

计算m[i][j]：

m[i][j] = m[i][j - 1] + pos[j] - pos[(i + j) >> 1];

考虑三个村庄1，2，3。那么最优选择是建立在2，当多了一个村庄4，其实还是建在2，那么只是多出了4到2的距离。

如果原来是1，2，3，4。最初是建在2和3都一样，一开始肯定建在(1 + 4) / 2的位置，也就是2，现在多了一个村庄5，那么最优选择是建在3，前四个的距离是没有变化的，仍然只是多出了5到3的距离，也就是上面表达式的内容。

状态转移方程是

d[i][j] = min(d[i][j], d[k][j - 1] + m[k + 1][i]);

也就是在前k个村庄建立j-1个学校，后面的村庄只建立一个学校。

时间复杂度$O(n^2m)$，其中m是学校的数量。

这个还是放在区间DP里面总结，不建议放在递推里面