企业官网建设流程全解析

题目描述

McBurger\texttt{McBurger}McBurger快餐连锁店在高速公路旁有nnn家餐厅，位置按递增顺序给出。公司决定在其中kkk家餐厅的位置建立仓库，每个餐厅分配到最近的仓库。目标是使所有餐厅到其分配仓库的距离之和最小，并输出每个仓库的位置及其服务的餐厅范围（连续的区间）。若有多组最优解，输出任意一组。

输入格式

多组测试数据。每组第一行为两个整数nnn和kkk（1≤n≤2001 \le n \le 2001≤n≤200，1≤k≤301 \le k \le 301≤k≤30，k≤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个仓库对应的前一个仓库位置（即上一段的结束点），以便回溯输出方案。

解题思路

预处理

1. 位置归一化：将位置减去dist[1]，使第一个位置为000，不影响距离计算。
2. 区间距离：interval[a][b] = abs(dist[a] - dist[b])。
3. 前缀距离：tds[i][j]表示若第iii个点为仓库，服务从111到jjj（或jjj到NNN）的所有点到仓库iii的距离之和，但代码中更细致地计算了部分贡献。

动态规划

• 状态定义：dp[i][j]表示选择iii个仓库，最后一个仓库设在位置jjj时的最小总距离。
• 转移：对于已有iii个仓库，最后一个仓库在jjj，尝试将第i+1i+1i+1个仓库设在kkk（k>jk > jk>j），则新的总距离 = 旧总距离 - 原先由最后一个仓库jjj服务的右侧部分（j+1j+1j+1到NNN的距离贡献） + 新仓库kkk服务j+1j+1j+1到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≤200，K≤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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintINF=0x3f3f3f3f;structstate{intsum,pre_depot;};intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0;intN,K,dist[210],interval[210][210],tds[210][210];state dp[210][210];while(cin>>N>>K){if(N==0)break;for(inti=1;i<=N;i++){cin>>dist[i];if(i>1)dist[i]-=dist[1];}dist[1]=0;for(inti=1;i<=N;i++)for(intj=i;j<=N;j++)interval[i][j]=interval[j][i]=abs(dist[i]-dist[j]);for(inti=1;i<=N;i++)for(intj=1;j<=N;j++){tds[i][j]=0;for(intk=min(i,j);k<=max(i,j);k++)tds[i][j]+=interval[k][i];}memset(dp,0x3f,sizeof(dp));for(inti=1;i<=N;i++){dp[1][i].sum=tds[i][1]+tds[i][N];dp[1][i].pre_depot=i;}for(inti=1;i<K;i++)for(intj=1;j<=N;j++){if(dp[i][j].sum==INF)continue;for(intk=j+1;k<=N;k++){intnew_sum=dp[i][j].sum-tds[j][N];for(intl=j+1;l<k;l++)new_sum+=min(interval[l][j],interval[l][k]);new_sum+=tds[k][N];if(new_sum<dp[i+1][k].sum){dp[i+1][k].sum=new_sum;dp[i+1][k].pre_depot=j;}}}cout<<"Chain "<<++cases<<'\n';intminimal_sum=INF,last_depot=-1;for(inti=1;i<=N;i++)if(minimal_sum>dp[K][i].sum){minimal_sum=dp[K][i].sum;last_depot=i;}vector<int>all_depot;intidx=K;while(idx){all_depot.push_back(last_depot);last_depot=dp[idx--][last_depot].pre_depot;}reverse(all_depot.begin(),all_depot.end());vector<int>served[all_depot.size()];intstart,end,pre_depot,next_depot,pre_i,next_i;for(inti=0;i<all_depot.size();i++){if(i==0)start=1;elsestart=all_depot[i];if(i==all_depot.size()-1)end=N;elseend=all_depot[i+1];pre_depot=all_depot[i];if(i==all_depot.size()-1)next_depot=all_depot[i];elsenext_depot=all_depot[i+1];pre_i=i;if(i==all_depot.size()-1)next_i=i;elsenext_i=i+1;for(intj=start;j<=end;j++){if(interval[j][pre_depot]<interval[j][next_depot])served[pre_i].push_back(j);elseserved[next_i].push_back(j);}}for(inti=0;i<all_depot.size();i++){cout<<"Depot "<<(i+1);cout<<" at restaurant "<<all_depot[i];cout<<" serves ";if(served[i].front()==served[i].back()){cout<<"restaurant ";cout<<served[i].front();}else{cout<<"restaurants ";cout<<served[i].front()<<" to "<<served[i].back();}cout<<'\n';}cout<<"Total distance sum = "<<minimal_sum<<'\n';cout<<'\n';}return0;}

总结

本题通过动态规划求解一维kkk-中心问题，并输出最优方案。关键点包括：

• 将餐厅位置排序，利用最优划分的连续性。
• 预处理区间内点到某点的距离之和，加速DP\texttt{DP}DP转移。
• 记录前驱状态以便回溯输出仓库位置。
• 根据仓库位置将点分配到最近仓库，得到服务区间。

该解法是经典DP\texttt{DP}DP的典型应用，适合N≤200N \le 200N≤200的规模。输出格式需注意单复数及区间范围。