题目描述
你正在为Maple mPhone\texttt{Maple mPhone}Maple mPhone开发一款名为Moogle Maps\texttt{Moogle Maps}Moogle Maps的地图软件。 该软件需要能够显示像“主街131313号”这样的房屋地址位置。 但由于手机存储容量有限， 你不能存储每个房屋的精确位置， 而是只存储一个子集的位置， 其余房屋的位置通过线性插值得到。 你的目标是选择要存储的房屋位置， 使得所有房屋的平均插值误差最小。 街道被视为一条直线， 并且你必须始终存储第一个和最后一个房屋的位置。
给定你存储了房屋iii和jjj的位置xix_ixi和xjx_jxj， 且它们之间没有存储其他房屋， 则对于房屋编号kkk（满足i<k<ji < k < ji<k<j）， 其插值位置为：
xi+(xj−xi)⋅k−ij−i x_i + (x_j - x_i) \cdot \frac{k-i}{j-i}xi+(xj−xi)⋅j−ik−i
输入格式
第一行包含一个整数ttt（1≤t≤501 \leq t \leq 501≤t≤50）， 表示测试用例的数量。
每个测试用例包含两行。 第一行包含两个整数hhh和ccc（2≤h≤2002 \leq h \leq 2002≤h≤200，2≤c≤h2 \leq c \leq h2≤c≤h）， 其中hhh是街道上的房屋数量，ccc是可以存储的房屋位置数量。 第二行包含hhh个按递增顺序排列的整数， 表示每个房屋的位置， 每个位置在区间[0,1000000][0, 1000000][0,1000000]内。
输出格式
对于每个测试用例， 输出在最优选择ccc个房屋位置存储的情况下， 所有hhh个房屋的平均插值误差。 输出应保留四位小数， 允许±0.001\pm 0.001±0.001的误差。
题目分析
这是一个典型的动态规划问题， 需要在必须选择第一个和最后一个房屋位置的约束下， 从hhh个点中选择ccc个点进行存储， 使得所有点的插值误差（绝对误差）的平均值最小。
核心思路
误差计算： 如果选择存储房屋iii和jjj（i<ji < ji<j）， 且它们之间没有其他存储点， 则对于中间的任何房屋kkk（i<k<ji < k < ji<k<j）， 其插值误差为∣xk−(xi+(xj−xi)⋅k−ij−i)∣\lvert x_k - (x_i + (x_j - x_i) \cdot \frac{k-i}{j-i}) \rvert∣xk−(xi+(xj−xi)⋅j−ik−i)∣。 我们可以预先计算任意两点iii和jjj作为相邻存储点时， 中间所有房屋的误差和， 记为error[i][j]error[i][j]error[i][j]。
动态规划状态定义： 定义dp[i][k]dp[i][k]dp[i][k]表示以房屋iii作为第kkk个被存储的点时， 前iii个房屋（包括iii）的最小总误差和。 这里“第kkk个”意味着我们总共选择了kkk个存储点， 并且最后一个点正好是iii。
状态转移方程： 要计算dp[i][k]dp[i][k]dp[i][k]， 我们需要考虑上一个存储点jjj（j<ij < ij<i）， 且jjj是第k−1k-1k−1个存储点。 那么从jjj到iii之间的房屋（不包括jjj和iii）的误差就是error[j][i]error[j][i]error[j][i]。 因此， 状态转移方程为：
dp[i][k]=min0≤j<i{dp[j][k−1]+error[j][i]} dp[i][k] = \min_{0 \leq j < i} \{ dp[j][k-1] + error[j][i] \}dp[i][k]=0≤j<imin{dp[j][k−1]+error[j][i]}边界条件： 由于第一个房屋必须被存储， 所以dp[0][1]=0dp[0][1] = 0dp[0][1]=0。 其他状态初始化为一个很大的值（表示不可达或误差无穷大）。
最终答案： 由于最后一个房屋也必须被存储， 我们需要的是dp[h−1][c]dp[h-1][c]dp[h−1][c]， 即最后一个房屋是第ccc个存储点时的最小总误差。 平均误差即为dp[h−1][c]/hdp[h-1][c] / hdp[h−1][c]/h。
算法步骤
- 读取输入数据。
- 对于每个测试用例：
- 读取hhh,ccc和房屋位置数组loclocloc。
- 预处理计算errorerrorerror矩阵： 对于所有0≤i<j<h0 \leq i < j < h0≤i<j<h， 计算error[i][j]error[i][j]error[i][j]。
- 初始化dpdpdp数组为无穷大， 设置dp[0][1]=0dp[0][1] = 0dp[0][1]=0。
- 进行动态规划： 遍历iii从000到h−1h-1h−1，kkk从111到ccc， 对于每个合法的dp[i][k]dp[i][k]dp[i][k]， 尝试将其状态转移到所有j>ij > ij>i作为下一个存储点。
- 计算平均误差dp[h−1][c]/hdp[h-1][c] / hdp[h−1][c]/h并输出。
- 输出结果保留四位小数。
复杂度分析
- 时间复杂度： 预处理errorerrorerror矩阵需要O(h3)O(h^3)O(h3)， 动态规划需要O(h2c)O(h^2 c)O(h2c)。 由于h≤200h \leq 200h≤200，c≤hc \leq hc≤h， 总计算量在可接受范围内。
- 空间复杂度： 需要O(h2)O(h^2)O(h2)存储errorerrorerror矩阵和O(h×c)O(h \times c)O(h×c)存储dpdpdp数组。
代码实现
// Moogle// UVa ID: 11370// Verdict: Accepted// Submission Date: 2025-12-20// UVa Run Time: 0.040s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;doublesolve(){inth,c;cin>>h>>c;vector<double>loc(h);for(inti=0;i<h;i++)cin>>loc[i];// 计算误差矩阵：error[i][j] 表示存储点 i 和 j 之间（不包括 i, j）的误差和vector<vector<double>>error(h,vector<double>(h,0.0));for(inti=0;i<h;i++){for(intj=i+1;j<h;j++){doublesum=0.0;for(intk=i+1;k<j;k++){// 计算房屋 k 的插值位置doubleinterp=loc[i]+(loc[j]-loc[i])*(k-i)/double(j-i);sum+=fabs(interp-loc[k]);// 累加绝对误差}error[i][j]=sum;}}// dp[i][k]: 以房屋 i 作为第 k 个存储点的最小误差和vector<vector<double>>dp(h,vector<double>(c+1,1e30));dp[0][1]=0.0;// 第一个房屋是第一个存储点，误差为0// 动态规划for(inti=0;i<h;i++){for(intk=1;k<=c;k++){if(dp[i][k]>1e29)continue;// 不可达状态// 尝试将 i 作为当前最后一个存储点，选择下一个存储点 jfor(intj=i+1;j<h;j++){if(k+1<=c){dp[j][k+1]=min(dp[j][k+1],dp[i][k]+error[i][j]);}}}}// 最后一个房屋必须是第 c 个存储点returndp[h-1][c]/h;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout<<fixed<<setprecision(4);intt;cin>>t;while(t--)cout<<solve()<<"\n";return0;}总结
本题的关键在于将问题转化为一个动态规划模型， 并正确处理必须选择首尾房屋的约束条件。 通过预处理任意两点作为相邻存储点时的误差和， 我们可以高效地进行状态转移。 算法的时间复杂度对于题目给定的数据范围是完全可行的。 注意在实现时， 要使用double类型来存储误差值， 并在输出时控制精度。