UVa 662 - Fast Food | Sengxian's Blog

UVa 662 - Fast Food

#数学 #DP

Published on 2016-02-14

描述

现在有 $n(1\le n\le200)$ 个餐馆，要在某些餐馆建共 $k(1\le k\le n)$ 个仓库，每个餐馆都到最近的仓库拿货，问怎么建仓库，才能使得所有餐馆到仓库的距离总和最小。

样例输入

样例输出

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

分析

因为不可能某个餐馆跨越仓库拿货的情况，即每个仓库就会形成一个不重叠的区间，这正是区间 DP 的明显特征！
设 $dp[i][j]$ 在前 $i$ 个餐馆建立 $j$ 个仓库的最小距离和，再设 $\mathrm{cost}(i, j)$ 为在区间 $[i, j]$ 建一个仓库的最小距离和，则方程很好写：

$\mathrm{cost}(i, j)$ 怎么求呢，难道要枚举在哪一个村庄建吗？不用。
如果我们在村庄 $k$ 建立，那么距离和就是：

\sum\limits_{i\le p\le j}\left\vert pos[p] - pos[k] \right\vert

如果我们把点画在数轴上，现在就变成了选择一个点，使得所有点到它的距离最短。先从小的情况出发。
如果只有两个点，只要选择的点在两个点形成的区间内（包含端点），距离和就是他们之间的距离，一旦出了这个区间，距离就大了，所以两个点任何一个都可以选。

如果有三个点，只要选择中间的点就行。

如果有更多的点，不难发现规律，如果是奇数个点，选择最中间的点；如果是偶数个点，选择中间两个点中之间的任意一个点都可以。

回到本题，由于只能在已有的点上面建餐馆，所以总是选择最中间的点就行了。
每个状态记录一下决策，递归输出解即可（注意每句话要打对啊！）。最终复杂度 $O(n^{2}k)$ 。

代码

//  Created by Sengxian on 2/14/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 662 DP + 决策优化
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar(); bool flag = false;
    while(!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return flag ? -n : n;
}
const int maxn = 200 + 3, maxk = 30 + 3, INF = 0x3f3f3f3f;
int n, K, pos[maxn], sum[maxn];
int dp[maxn][maxk];
typedef pair<int, int> state;
state choice[maxn][maxk];

inline int Sum(int i, int j) {
    return sum[j] - sum[i - 1];
}

inline int cost(int i, int j, int &c) {
    c = (i + j) / 2; //选择中位数建立
    return pos[c] * (2 * c - i - j) - Sum(i, c - 1) + Sum(c + 1, j);
}

void print(int i, int j) {
    if(i == 0 && j == 0) return;
    print(choice[i][j].first - 1, j - 1);
    if(choice[i][j].first == i) printf("Depot %d at restaurant %d serves restaurant %d\n", j, choice[i][j].second, i);
    else printf("Depot %d at restaurant %d serves restaurants %d to %d\n", j, choice[i][j].second, choice[i][j].first, i);
}

void solve() {
    memset(dp[0], INF, sizeof(dp[0]));
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i) {
        memset(dp[i], INF, sizeof(dp[i]));
        for(int j = 1; j <= min(K, i); ++j)
            for(int k = j; k <= i; ++k) {
                int c, val = dp[k - 1][j - 1] + cost(k, i, c);
                if(val < dp[i][j]) choice[i][j] = state(k, c), dp[i][j] = val;
            }
    }
    print(n, K);
    printf("Total distance sum = %d\n\n", dp[n][K]);
}

int main() {
    int caseNum = 0;
    while(n = ReadInt(), K = ReadInt(), n + K) {
        sum[0] = 0;
        for(int i = 1; i <= n; ++i)
            sum[i] = (pos[i] = ReadInt()) + sum[i - 1];
        printf("Chain %d\n", ++caseNum);
        solve();
    }
    return 0;
}

附加输入

200 10
41 53 153 288 292 467 491 778 900 1150
1655 1842 1869 1999 2082 2306 2421 2995 3035 3430
3548 3602 3728 3788 3902 4031 4041 4596 4639 4664
4734 4827 4833 4966 5021 5097 5436 5447 5537 5705
5829 6270 6334 6359 6422 6483 6617 6729 6868 6900
7376 7711 8281 8723 8909 8942 9040 9161 9374 9514
9741 9758 9894 9930 9961 10291 10383 11020 11323 11337
11478 11538 11840 11942 12052 12287 12316 12382 12623 12859
13030 13290 13931 13966 13977 14310 14604 14771 14893 14945
15006 15141 15350 15457 15573 15574 15724 15890 16118 16413
16512 16541 16827 16941 16944 17035 17410 17421 17673 17807
18007 18127 18467 18588 18636 18716 18756 18762 19072 19169
19264 19629 19668 19718 19895 19912 19954 20037 20537 21538
21548 21724 21726 22190 22355 22386 22483 22648 22704 22813
22929 23199 23281 23655 23805 23811 23986 24021 24084 24221
24350 24370 24393 24464 24484 24626 24648 24767 24946 25547
25667 26299 26308 26418 26500 26777 26924 26962 27348 27350
27446 27506 27529 27595 27624 27644 27753 27938 28145 28253
28703 28745 29168 29358 29658 30106 30191 30333 30836 31101
31107 31115 31322 31673 32209 32391 32439 32591 32662 32757
200 20
41 53 153 288 292 467 491 778 900 1150
1655 1842 1869 1999 2082 2306 2421 2995 3035 3430
3548 3602 3728 3788 3902 4031 4041 4596 4639 4664
4734 4827 4833 4966 5021 5097 5436 5447 5537 5705
5829 6270 6334 6359 6422 6483 6617 6729 6868 6900
7376 7711 8281 8723 8909 8942 9040 9161 9374 9514
9741 9758 9894 9930 9961 10291 10383 11020 11323 11337
11478 11538 11840 11942 12052 12287 12316 12382 12623 12859
13030 13290 13931 13966 13977 14310 14604 14771 14893 14945
15006 15141 15350 15457 15573 15574 15724 15890 16118 16413
16512 16541 16827 16941 16944 17035 17410 17421 17673 17807
18007 18127 18467 18588 18636 18716 18756 18762 19072 19169
19264 19629 19668 19718 19895 19912 19954 20037 20537 21538
21548 21724 21726 22190 22355 22386 22483 22648 22704 22813
22929 23199 23281 23655 23805 23811 23986 24021 24084 24221
24350 24370 24393 24464 24484 24626 24648 24767 24946 25547
25667 26299 26308 26418 26500 26777 26924 26962 27348 27350
27446 27506 27529 27595 27624 27644 27753 27938 28145 28253
28703 28745 29168 29358 29658 30106 30191 30333 30836 31101
31107 31115 31322 31673 32209 32391 32439 32591 32662 32757
200 30
41 53 153 288 292 467 491 778 900 1150
1655 1842 1869 1999 2082 2306 2421 2995 3035 3430
3548 3602 3728 3788 3902 4031 4041 4596 4639 4664
4734 4827 4833 4966 5021 5097 5436 5447 5537 5705
5829 6270 6334 6359 6422 6483 6617 6729 6868 6900
7376 7711 8281 8723 8909 8942 9040 9161 9374 9514
9741 9758 9894 9930 9961 10291 10383 11020 11323 11337
11478 11538 11840 11942 12052 12287 12316 12382 12623 12859
13030 13290 13931 13966 13977 14310 14604 14771 14893 14945
15006 15141 15350 15457 15573 15574 15724 15890 16118 16413
16512 16541 16827 16941 16944 17035 17410 17421 17673 17807
18007 18127 18467 18588 18636 18716 18756 18762 19072 19169
19264 19629 19668 19718 19895 19912 19954 20037 20537 21538
21548 21724 21726 22190 22355 22386 22483 22648 22704 22813
22929 23199 23281 23655 23805 23811 23986 24021 24084 24221
24350 24370 24393 24464 24484 24626 24648 24767 24946 25547
25667 26299 26308 26418 26500 26777 26924 26962 27348 27350
27446 27506 27529 27595 27624 27644 27753 27938 28145 28253
28703 28745 29168 29358 29658 30106 30191 30333 30836 31101
31107 31115 31322 31673 32209 32391 32439 32591 32662 32757
0 0

附加输出

Chain 1
Depot 1 at restaurant 9 serves restaurants 1 to 17
Depot 2 at restaurant 34 serves restaurants 18 to 50
Depot 3 at restaurant 59 serves restaurants 51 to 67
Depot 4 at restaurant 75 serves restaurants 68 to 82
Depot 5 at restaurant 94 serves restaurants 83 to 106
Depot 6 at restaurant 118 serves restaurants 107 to 129
Depot 7 at restaurant 136 serves restaurants 130 to 143
Depot 8 at restaurant 152 serves restaurants 144 to 161
Depot 9 at restaurant 172 serves restaurants 162 to 183
Depot 10 at restaurant 192 serves restaurants 184 to 200
Total distance sum = 144490

Chain 2
Depot 1 at restaurant 5 serves restaurants 1 to 9
Depot 2 at restaurant 13 serves restaurants 10 to 17
Depot 3 at restaurant 22 serves restaurants 18 to 27
Depot 4 at restaurant 34 serves restaurants 28 to 40
Depot 5 at restaurant 46 serves restaurants 41 to 52
Depot 6 at restaurant 56 serves restaurants 53 to 59
Depot 7 at restaurant 63 serves restaurants 60 to 67
Depot 8 at restaurant 74 serves restaurants 68 to 80
Depot 9 at restaurant 84 serves restaurants 81 to 87
Depot 10 at restaurant 93 serves restaurants 88 to 99
Depot 11 at restaurant 105 serves restaurants 100 to 110
Depot 12 at restaurant 116 serves restaurants 111 to 121
Depot 13 at restaurant 125 serves restaurants 122 to 129
Depot 14 at restaurant 136 serves restaurants 130 to 143
Depot 15 at restaurant 151 serves restaurants 144 to 159
Depot 16 at restaurant 164 serves restaurants 160 to 168
Depot 17 at restaurant 174 serves restaurants 169 to 180
Depot 18 at restaurant 184 serves restaurants 181 to 187
Depot 19 at restaurant 191 serves restaurants 188 to 194
Depot 20 at restaurant 197 serves restaurants 195 to 200
Total distance sum = 64170

Chain 3
Depot 1 at restaurant 4 serves restaurants 1 to 7
Depot 2 at restaurant 9 serves restaurants 8 to 10
Depot 3 at restaurant 14 serves restaurants 11 to 17
Depot 4 at restaurant 22 serves restaurants 18 to 27
Depot 5 at restaurant 32 serves restaurants 28 to 36
Depot 6 at restaurant 39 serves restaurants 37 to 41
Depot 7 at restaurant 46 serves restaurants 42 to 50
Depot 8 at restaurant 52 serves restaurants 51 to 53
Depot 9 at restaurant 56 serves restaurants 54 to 59
Depot 10 at restaurant 63 serves restaurants 60 to 67
Depot 11 at restaurant 70 serves restaurants 68 to 72
Depot 12 at restaurant 77 serves restaurants 73 to 81
Depot 13 at restaurant 84 serves restaurants 82 to 86
Depot 14 at restaurant 89 serves restaurants 87 to 92
Depot 15 at restaurant 96 serves restaurants 93 to 99
Depot 16 at restaurant 103 serves restaurants 100 to 106
Depot 17 at restaurant 109 serves restaurants 107 to 112
Depot 18 at restaurant 117 serves restaurants 113 to 121
Depot 19 at restaurant 125 serves restaurants 122 to 129
Depot 20 at restaurant 131 serves restaurants 130 to 133
Depot 21 at restaurant 138 serves restaurants 134 to 142
Depot 22 at restaurant 146 serves restaurants 143 to 149
Depot 23 at restaurant 154 serves restaurants 150 to 159
Depot 24 at restaurant 160 serves restaurants 160 to 161
Depot 25 at restaurant 165 serves restaurants 162 to 168
Depot 26 at restaurant 174 serves restaurants 169 to 179
Depot 27 at restaurant 182 serves restaurants 180 to 184
Depot 28 at restaurant 186 serves restaurants 185 to 188
Depot 29 at restaurant 191 serves restaurants 189 to 194
Depot 30 at restaurant 197 serves restaurants 195 to 200
Total distance sum = 39563

UVa 10892 - LCM Cardinality Dynamic Programming Exercises Beginner 归档题解(3)