UVa 11370 Moogle-育师

题目描述

你正在为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]=min⁡0≤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;}