UVa 662 - Fast Food
传送门
题意
现在有A个饭店和B个仓库，求把B个仓库建在什么地方，使得各个饭店到最近的仓库的距离之和最小。
思路
参考了shuangde800的解题报告。
先求出每个i~j的最短距离，然后对每个区间进行DP。
状态转移方程$dp[i][j] = dp[k - 1][j - 1] + dis[k][i]$，$dp[i][j]$表示前i个饭店里选择j个仓库的最小距离。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250;
const int INF = 0x3f3f3f3f;
int dis[MAXN][MAXN], dp[MAXN][40], shop[MAXN], range[MAXN][MAXN], cas = 1;
void PrintAns(int i, int j)
{
if (i < 1 || j < 1)
return;
PrintAns(range[i][j] - 1, j - 1);
printf("Depot %d at restaurant %d serves restaurant", cas++, (range[i][j] + i) / 2);
if (range[i][j] == i)
printf(" %d\n", i);
else
printf("s %d to %d\n", range[i][j], i);
}
int main()
{
//freopen("input.txt", "r", stdin);
int n, k, i, j, cases = 0;
while (scanf("%d%d", &n, &k), n + k)
{
memset(dp, INF, sizeof dp);
memset(dp[0], 0, sizeof dp[0]);
memset(dis, 0, sizeof dis);
for (i = 1; i <= n; i++)
scanf("%d", &shop[i]);
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++)
{
int mid = (i + j) >> 1;
for (int ii = i; ii <= j; ii++)
dis[i][j] += abs(shop[ii] - shop[mid]);
}
for (i = 1; i <= n; i++)
for (j = 1; j <= k; j++)
for (int ii = 1; ii <= i; ii++)
{
if (dp[ii - 1][j - 1] + dis[ii][i] < dp[i][j])
{
dp[i][j] = dp[ii - 1][j - 1] + dis[ii][i];
range[i][j] = ii;
}
}
cas = 1;
printf("Chain %d\n", ++cases);
PrintAns(n, k);
printf("Total distance sum = %d\n\n", dp[n][k]);
}
return 0;
}