题目描述McBurger\texttt{McBurger}McBurger快餐连锁店在高速公路旁有nnn家餐厅位置按递增顺序给出。公司决定在其中kkk家餐厅的位置建立仓库每个餐厅分配到最近的仓库。目标是使所有餐厅到其分配仓库的距离之和最小并输出每个仓库的位置及其服务的餐厅范围连续的区间。若有多组最优解输出任意一组。输入格式多组测试数据。每组第一行为两个整数nnn和kkk1≤n≤2001 \le n \le 2001≤n≤2001≤k≤301 \le k \le 301≤k≤30k≤nk \le nk≤n。接下来nnn行每行一个整数表示餐厅位置递增。输入以0 0结束。输出格式对于每组数据输出Chain X:其中XXX为数据组编号从111开始。然后输出kkk行每行描述一个仓库的位置和服务范围如Depot Y at restaurant Z serves restaurants L to R或单个餐厅。最后输出一行Total distance sum S。每组输出后跟一个空行。样例输入6 3 5 6 12 19 20 27 0 0输出Chain 1 Depot 1 at restaurant 2 serves restaurants 1 to 3 Depot 2 at restaurant 4 serves restaurants 4 to 5 Depot 3 at restaurant 6 serves restaurant 6 Total distance sum 8题目分析本题是经典的“一维kkk-中心”问题需要在数轴上选择kkk个点必须是给定点将nnn个点划分到kkk个簇每个簇由连续的一段点组成且每个簇的中心取该段中某个点仓库位置使得所有点到其簇中心的绝对距离之和最小。由于点按位置排序最优划分必然将排序后的点分成kkk个连续段每段由一个仓库服务。动态规划可解。设dp[i][j]dp[i][j]dp[i][j]表示前jjj个点111到jjj用iii个仓库时的最小总距离同时记录第iii个仓库对应的前一个仓库位置即上一段的结束点以便回溯输出方案。解题思路预处理位置归一化将位置减去dist[1]使第一个位置为000不影响距离计算。区间距离interval[a][b] abs(dist[a] - dist[b])。前缀距离tds[i][j]表示若第iii个点为仓库服务从111到jjj或jjj到NNN的所有点到仓库iii的距离之和但代码中更细致地计算了部分贡献。动态规划状态定义dp[i][j]表示选择iii个仓库最后一个仓库设在位置jjj时的最小总距离。转移对于已有iii个仓库最后一个仓库在jjj尝试将第i1i1i1个仓库设在kkkkjk jkj则新的总距离 旧总距离 - 原先由最后一个仓库jjj服务的右侧部分j1j1j1到NNN的距离贡献 新仓库kkk服务j1j1j1到k−1k-1k−1的最优分配取到jjj或kkk的较小者 新仓库kkk服务kkk到NNN的距离。该转移比较繁琐但本质是标准的区间DP\texttt{DP}DP。输出方案通过记录每个状态的pre_depot前一个仓库位置从最优的dp[K][last]反向回溯得到所有仓库位置。然后根据仓库位置将每个点分配到最近的仓库若距离相等可任意分配得到每个仓库服务的连续区间按格式输出。复杂度分析状态数O(K⋅N)O(K \cdot N)O(K⋅N)转移O(N)O(N)O(N)总复杂度O(K⋅N2)O(K \cdot N^2)O(K⋅N2)N≤200N \le 200N≤200K≤30K \le 30K≤30完全可接受。空间复杂度O(K⋅N)O(K \cdot N)O(K⋅N)。代码实现// Fast Food// UVa ID: 662// Verdict: Accepted// Submission Date: 2018-09-15// UVa Run Time: 0.040s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintINF0x3f3f3f3f;structstate{intsum,pre_depot;};intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;intN,K,dist[210],interval[210][210],tds[210][210];state dp[210][210];while(cinNK){if(N0)break;for(inti1;iN;i){cindist[i];if(i1)dist[i]-dist[1];}dist[1]0;for(inti1;iN;i)for(intji;jN;j)interval[i][j]interval[j][i]abs(dist[i]-dist[j]);for(inti1;iN;i)for(intj1;jN;j){tds[i][j]0;for(intkmin(i,j);kmax(i,j);k)tds[i][j]interval[k][i];}memset(dp,0x3f,sizeof(dp));for(inti1;iN;i){dp[1][i].sumtds[i][1]tds[i][N];dp[1][i].pre_depoti;}for(inti1;iK;i)for(intj1;jN;j){if(dp[i][j].sumINF)continue;for(intkj1;kN;k){intnew_sumdp[i][j].sum-tds[j][N];for(intlj1;lk;l)new_summin(interval[l][j],interval[l][k]);new_sumtds[k][N];if(new_sumdp[i1][k].sum){dp[i1][k].sumnew_sum;dp[i1][k].pre_depotj;}}}coutChain cases\n;intminimal_sumINF,last_depot-1;for(inti1;iN;i)if(minimal_sumdp[K][i].sum){minimal_sumdp[K][i].sum;last_depoti;}vectorintall_depot;intidxK;while(idx){all_depot.push_back(last_depot);last_depotdp[idx--][last_depot].pre_depot;}reverse(all_depot.begin(),all_depot.end());vectorintserved[all_depot.size()];intstart,end,pre_depot,next_depot,pre_i,next_i;for(inti0;iall_depot.size();i){if(i0)start1;elsestartall_depot[i];if(iall_depot.size()-1)endN;elseendall_depot[i1];pre_depotall_depot[i];if(iall_depot.size()-1)next_depotall_depot[i];elsenext_depotall_depot[i1];pre_ii;if(iall_depot.size()-1)next_ii;elsenext_ii1;for(intjstart;jend;j){if(interval[j][pre_depot]interval[j][next_depot])served[pre_i].push_back(j);elseserved[next_i].push_back(j);}}for(inti0;iall_depot.size();i){coutDepot (i1);cout at restaurant all_depot[i];cout serves ;if(served[i].front()served[i].back()){coutrestaurant ;coutserved[i].front();}else{coutrestaurants ;coutserved[i].front() to served[i].back();}cout\n;}coutTotal distance sum minimal_sum\n;cout\n;}return0;}总结本题通过动态规划求解一维kkk-中心问题并输出最优方案。关键点包括将餐厅位置排序利用最优划分的连续性。预处理区间内点到某点的距离之和加速DP\texttt{DP}DP转移。记录前驱状态以便回溯输出仓库位置。根据仓库位置将点分配到最近仓库得到服务区间。该解法是经典DP\texttt{DP}DP的典型应用适合N≤200N \le 200N≤200的规模。输出格式需注意单复数及区间范围。