// Problem : 662 - Fast Food
// Contest : UVa Online Judge
// URL : https://o...content-available-to-author-only...e.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=603
// Memory Limit : 32 MB
// Time Limit : 3000 ms
// Powered by CP Editor (https://g...content-available-to-author-only...b.com/cpeditor/cpeditor)
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define Ma7moud_7amdy \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define Open_Sesame Open()
#define all(v) ((v).begin()), ((v).end())
#define allr(v) ((v).rbegin()), ((v).rend())
#define clr(arr, x) memset(arr, x, sizeof arr)
#define endl "\n"
#define watch(x) cout << #x << " = " << x << endl;
#define RT(x) return cout << (x), 0;
#define Accepted 0
#define INF 0x3f3f3f3f3f3f3f3fLL
typedef long long ll;
typedef vector<int> vi;
const int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
void Open()
{
#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
}
const int mod = ll(1e9 + 7), N = 2000 + 5;
//“Nobody but you have to believe in your dreams to make them a reality.” ― Germany Kent
int n, k;
ll mem[201][201][31], vis[201][201][31], T = 0;
vector<int>v;
ll solve(int i, int lst, int rem) {
if (rem < 0)return 1e17;
if (i == n) {
return (rem == 0 && lst == i ? 0 : 1e17);
}
ll& ret = mem[i][lst][rem];
if (vis[i][lst][rem] == T)return ret;
vis[i][lst][rem] = T;
ret = 1e17;
ret = min(ret, solve(i + 1, lst, rem));
ll mnSum = 1e17;
ll curSum = 0;
for (int j = lst; j <= i; j++) {
curSum += abs(v[j] - v[lst]);
}
mnSum = min(curSum, mnSum);
for (int nxt = lst + 1; nxt <= i; nxt++) {
ll curSum = mnSum + 1LL * abs(v[nxt] - v[lst]) * (nxt - lst) - 1LL * abs(v[nxt] - v[lst]) * (i - nxt + 1);
mnSum = min(curSum, mnSum);
}
ret = min(ret, solve(i + 1, i + 1, rem - 1) + mnSum);
return ret;
}
int dCur = 0;
void build(int i, int lst, int rem) {
if (rem < 0)return;
if (i == n) {
return;
}
ll ret = mem[i][lst][rem];
if (ret == solve(i + 1, lst, rem))return build(i + 1, lst, rem);
ll mnSum = 1e17;
ll curSum = 0;
for (int j = lst; j <= i; j++) {
curSum += abs(v[j] - v[lst]);
}
mnSum = min(curSum, mnSum);
int idx = lst + 1;
for (int nxt = lst + 1; nxt <= i; nxt++) {
ll curSum = mnSum + 1LL * abs(v[nxt] - v[lst]) * (nxt - lst) - 1LL * abs(v[nxt] - v[lst]) * (i - nxt + 1);
mnSum = min(curSum, mnSum);
if (mnSum == curSum)idx = nxt + 1;
}
if (ret == solve(i + 1, i + 1, rem - 1) + mnSum) {
cout << "Depot " << ++dCur << " at restaurant " << idx;
if (lst != i)
cout << " serves restaurants " << lst + 1 << " to " << i + 1 << endl;
else
cout << " serves restaurant " << lst + 1 << endl;
build(i + 1, i + 1, rem - 1);
}
return;
}
int main()
{
Ma7moud_7amdy;
Open_Sesame;
while (cin >> n >> k && n && ++T) {
dCur = 0;;
v = vector<int>(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
ll ans = solve(0, 0, k);
cout << "Chain " << T << endl;
build(0, 0, k);
cout << "Total distance sum = " << ans << endl;
cout << endl;
}
}
Ci8vIFByb2JsZW0gOiA2NjIgLSBGYXN0IEZvb2QKLy8gQ29udGVzdCA6IFVWYSBPbmxpbmUgSnVkZ2UKLy8gVVJMIDogaHR0cHM6Ly9vLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLm9yZy9pbmRleC5waHA/b3B0aW9uPWNvbV9vbmxpbmVqdWRnZSZJdGVtaWQ9OCZwYWdlPXNob3dfcHJvYmxlbSZwcm9ibGVtPTYwMwovLyBNZW1vcnkgTGltaXQgOiAzMiBNQgovLyBUaW1lIExpbWl0IDogMzAwMCBtcwovLyBQb3dlcmVkIGJ5IENQIEVkaXRvciAoaHR0cHM6Ly9nLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5iLmNvbS9jcGVkaXRvci9jcGVkaXRvcikKCiNkZWZpbmUgX0NSVF9TRUNVUkVfTk9fV0FSTklOR1MKI2RlZmluZSBfVVNFX01BVEhfREVGSU5FUwojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgojaW5jbHVkZTx1bm9yZGVyZWRfbWFwPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIE1hN21vdWRfN2FtZHkgICAgICAgICAgICAgICAgIFwKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBcCiAgICBjaW4udGllKE5VTEwpOyAgICAgICAgICAgICAgICAgICAgXAogICAgY291dC50aWUoTlVMTCkKI2RlZmluZSBPcGVuX1Nlc2FtZSBPcGVuKCkKI2RlZmluZSBhbGwodikgKCh2KS5iZWdpbigpKSwgKCh2KS5lbmQoKSkKI2RlZmluZSBhbGxyKHYpICgodikucmJlZ2luKCkpLCAoKHYpLnJlbmQoKSkKI2RlZmluZSBjbHIoYXJyLCB4KSBtZW1zZXQoYXJyLCB4LCBzaXplb2YgYXJyKQojZGVmaW5lIGVuZGwgIlxuIgojZGVmaW5lIHdhdGNoKHgpIGNvdXQgPDwgI3ggPDwgIiA9ICIgPDwgeCA8PCBlbmRsOwojZGVmaW5lIFJUKHgpIHJldHVybiBjb3V0IDw8ICh4KSwgMDsKI2RlZmluZSBBY2NlcHRlZCAwCiNkZWZpbmUgSU5GIDB4M2YzZjNmM2YzZjNmM2YzZkxMCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwpjb25zdCBpbnQgZHhbXSA9IHsgMSwgMCwgLTEsIDAsIDEsIDEsIC0xLCAtMSB9Owpjb25zdCBpbnQgZHlbXSA9IHsgMCwgMSwgMCwgLTEsIDEsIC0xLCAxLCAtMSB9Owp2b2lkIE9wZW4oKQp7CiNpZm5kZWYgT05MSU5FX0pVREdFIAoJZnJlb3BlbigiSW5wdXQudHh0IiwgInIiLCBzdGRpbik7CglmcmVvcGVuKCJPdXRwdXQudHh0IiwgInciLCBzdGRvdXQpOwojZW5kaWYKfQpjb25zdCBpbnQgbW9kID0gbGwoMWU5ICsgNyksIE4gPSAyMDAwICsgNTsKLy/igJxOb2JvZHkgYnV0IHlvdSBoYXZlIHRvIGJlbGlldmUgaW4geW91ciBkcmVhbXMgdG8gbWFrZSB0aGVtIGEgcmVhbGl0eS7igJ0g4oCVIEdlcm1hbnkgS2VudAppbnQgbiwgazsKbGwgbWVtWzIwMV1bMjAxXVszMV0sIHZpc1syMDFdWzIwMV1bMzFdLCBUID0gMDsKCnZlY3RvcjxpbnQ+djsKbGwgc29sdmUoaW50IGksIGludCBsc3QsIGludCByZW0pIHsKCWlmIChyZW0gPCAwKXJldHVybiAxZTE3OwoJaWYgKGkgPT0gbikgewoJCXJldHVybiAocmVtID09IDAgJiYgbHN0ID09IGkgPyAwIDogMWUxNyk7Cgl9CglsbCYgcmV0ID0gbWVtW2ldW2xzdF1bcmVtXTsKCWlmICh2aXNbaV1bbHN0XVtyZW1dID09IFQpcmV0dXJuIHJldDsKCXZpc1tpXVtsc3RdW3JlbV0gPSBUOwoJcmV0ID0gMWUxNzsKCXJldCA9IG1pbihyZXQsIHNvbHZlKGkgKyAxLCBsc3QsIHJlbSkpOwoJbGwgbW5TdW0gPSAxZTE3OwoJbGwgY3VyU3VtID0gMDsKCWZvciAoaW50IGogPSBsc3Q7IGogPD0gaTsgaisrKSB7CgkJY3VyU3VtICs9IGFicyh2W2pdIC0gdltsc3RdKTsKCX0KCW1uU3VtID0gbWluKGN1clN1bSwgbW5TdW0pOwoJZm9yIChpbnQgbnh0ID0gbHN0ICsgMTsgbnh0IDw9IGk7IG54dCsrKSB7CgkJbGwgY3VyU3VtID0gbW5TdW0gKyAxTEwgKiBhYnModltueHRdIC0gdltsc3RdKSAqIChueHQgLSBsc3QpIC0gMUxMICogYWJzKHZbbnh0XSAtIHZbbHN0XSkgKiAoaSAtIG54dCArIDEpOwoJCW1uU3VtID0gbWluKGN1clN1bSwgbW5TdW0pOwoJfQoKCglyZXQgPSBtaW4ocmV0LCBzb2x2ZShpICsgMSwgaSArIDEsIHJlbSAtIDEpICsgbW5TdW0pOwoJcmV0dXJuIHJldDsKfQppbnQgZEN1ciA9IDA7CnZvaWQgYnVpbGQoaW50IGksIGludCBsc3QsIGludCByZW0pIHsKCWlmIChyZW0gPCAwKXJldHVybjsKCWlmIChpID09IG4pIHsKCQlyZXR1cm47Cgl9CglsbCByZXQgPSBtZW1baV1bbHN0XVtyZW1dOwoJaWYgKHJldCA9PSBzb2x2ZShpICsgMSwgbHN0LCByZW0pKXJldHVybiBidWlsZChpICsgMSwgbHN0LCByZW0pOwoJbGwgbW5TdW0gPSAxZTE3OwoJbGwgY3VyU3VtID0gMDsKCWZvciAoaW50IGogPSBsc3Q7IGogPD0gaTsgaisrKSB7CgkJY3VyU3VtICs9IGFicyh2W2pdIC0gdltsc3RdKTsKCX0KCW1uU3VtID0gbWluKGN1clN1bSwgbW5TdW0pOwoJaW50IGlkeCA9IGxzdCArIDE7Cglmb3IgKGludCBueHQgPSBsc3QgKyAxOyBueHQgPD0gaTsgbnh0KyspIHsKCQlsbCBjdXJTdW0gPSBtblN1bSArIDFMTCAqIGFicyh2W254dF0gLSB2W2xzdF0pICogKG54dCAtIGxzdCkgLSAxTEwgKiBhYnModltueHRdIC0gdltsc3RdKSAqIChpIC0gbnh0ICsgMSk7CgkJbW5TdW0gPSBtaW4oY3VyU3VtLCBtblN1bSk7CgkJaWYgKG1uU3VtID09IGN1clN1bSlpZHggPSBueHQgKyAxOwoJfQoJaWYgKHJldCA9PSBzb2x2ZShpICsgMSwgaSArIDEsIHJlbSAtIDEpICsgbW5TdW0pIHsKCQljb3V0IDw8ICJEZXBvdCAiIDw8ICsrZEN1ciA8PCAiIGF0IHJlc3RhdXJhbnQgIiA8PCBpZHg7CgkJaWYgKGxzdCAhPSBpKQoJCQljb3V0IDw8ICIgc2VydmVzIHJlc3RhdXJhbnRzICIgPDwgbHN0ICsgMSA8PCAiIHRvICIgPDwgaSArIDEgPDwgZW5kbDsKCQllbHNlCgkJCWNvdXQgPDwgIiBzZXJ2ZXMgcmVzdGF1cmFudCAiIDw8IGxzdCArIDEgPDwgZW5kbDsKCQlidWlsZChpICsgMSwgaSArIDEsIHJlbSAtIDEpOwoJfQoJcmV0dXJuOwp9CgppbnQgbWFpbigpCnsKCU1hN21vdWRfN2FtZHk7CglPcGVuX1Nlc2FtZTsKCgl3aGlsZSAoY2luID4+IG4gPj4gayAmJiBuICYmICsrVCkgewoJCWRDdXIgPSAwOzsKCQl2ID0gdmVjdG9yPGludD4obik7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKCQkJY2luID4+IHZbaV07CgkJfQoKCQlsbCBhbnMgPSBzb2x2ZSgwLCAwLCBrKTsKCQljb3V0IDw8ICJDaGFpbiAiIDw8IFQgPDwgZW5kbDsKCQlidWlsZCgwLCAwLCBrKTsKCQljb3V0IDw8ICJUb3RhbCBkaXN0YW5jZSBzdW0gPSAiIDw8IGFucyA8PCBlbmRsOwoJCWNvdXQgPDwgZW5kbDsKCX0KfQ==