信息学奥赛1197：山区建小学

### 关于信息学奥赛 NOIP “山区建小学” 的解法与思路 #### 问题描述 题目通常涉及在一个一维数组上选择若干位置建立学校，使得所有村庄到最近学校的距离之和最小化。这是一个经典的优化问题。 #### 解决方法概述 该问题可以通过动态规划来解决。以下是详细的分析： 1. **状态定义** 定义 `dp[i][k]` 表示前 `i` 个村庄建立了 `k` 所学校时的最优解（即总距离最短）。其中，`i` 是当前考虑的村庄编号，`k` 是已经建立的学校数量[^2]。 2. **转移方程** 对于每一个子问题 `dp[i][k]`，可以枚举第 `k` 所学校的位置 `j` （满足 `j ≤ i`），则有： \[ dp[i][k] = \min_{j} (dp[j-1][k-1] + cost(j, i)) \] 其中，`cost(j, i)` 表示从村庄 `j` 到村庄 `i` 如果只设立一所学校，则这些村庄到这所学校的总距离。 3. **预处理成本函数** 计算任意区间 `[l, r]` 内如果设置一所学校所需的总代价 `cost(l, r)` 可以通过二分查找找到最佳学校位置并计算相应距离。为了加速这一过程，可以利用前缀和技巧预先计算每两个村庄之间的绝对差值累积和。 4. **初始化条件** 当仅有一个村庄时 (`i=1`) ，无论建造多少所学校，其初始值都应设为零；当没有任何学校被建设时(`k=0`)，除了第一个村庄外其他地方的距离均为无穷大或者极大值表示不可达情况。 5. **最终答案获取** 结果存储在 `dp[n][m]` 中，这里 `n` 是总的村庄数目而 `m` 是允许的最大学校数。 ```python def solve(): n, m = map(int, input().split()) # 村庄数 和 学校数 pos = list(map(int, input().split())) # 每个村庄的位置 # 排序以便后续操作 pos.sort() # 初始化 cost 数组 cost = [[0]*(n+2) for _ in range(n+2)] prefix_sum = [0] * (n+1) for i in range(1, n+1): prefix_sum[i] = prefix_sum[i-1] + pos[i-1] def get_cost(l, r): # l,r 已经加1偏移量调整过了 mid = (l+r)//2 total = prefix_sum[r]-prefix_sum[l-1] median_pos = pos[mid-1] count = r-l+1 return abs(total - count*median_pos) for length in range(2,n+1): for start in range(1, n-length+2): end = start + length -1 cost[start][end]=get_cost(start,end) INF=float('inf') dp=[[INF]*(m+1)for _ in range(n+1)] for k in range(m+1): dp[0][k]=0 for i in range(1,n+1): for k in range(1,min(i,m)+1): for j in range(k,i+1): dp[i][k]= min(dp[i][k], dp[j-1][k-1]+cost[j][i]) print(dp[n][m]) ``` #### 时间复杂度分析 上述实现的时间复杂度主要由三重循环决定：外部两层遍历所有的 `(i,k)` 组合，内部一层用于寻找分割点 `j` 。因此总体时间复杂度大约为 O(N^2M)，对于较小规模的数据集是可以接受的。