10944 - Nuts for nuts..

位元DP。

我們定義 $dp[i][j] = k$, $j$ 為已經拾取過果實的地方，$i$ 為最後所停之處，$dp[i][j]$為拾取果實後停在$i$的總步數。

初始化的話，$dp[i][1<<i] = $ 從出發點到此的距離，其餘 $\infty$。

計算的話，假設我們有三個點，我們現在要求取$dp[0][3]$（已經在0, 1拿完果實，並停在0），那我們的其中一種可行走法為$dp[1][2] + dist[1][0]$，也就是說，從只去過1的狀態走到0來！所以更新的話，就是:

1
2


dp[i][j] = min(dp[i][j], dp[k][j - (1 << i)] + dist[i][k]);

AC Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int oo = 0x3f3f3f3f;

int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        int sx = -1, sy = -1;
        vector<ii> loc;
        for (int i = 0; i < n; i++) {
            char str[m + 2];
            scanf("%s", str);
            for (int j = 0; j < m; j++) {
                if (str[j] == 'L') {
                    sx = i;
                    sy = j;
                } else if (str[j] == '.') {
                } else {
                    loc.push_back(ii(i, j));
                }
            }
        }
        loc.push_back(ii(sx, sy));
        int pts = loc.size();

        // get dist
        int dist[pts][pts];
        for (int i = 0; i < pts; i++)
            fill(dist[i], dist[i] + pts, oo);

        for (int i = 0; i < pts; i++)
            for (int j = 0; j < pts; j++)
                dist[i][j] = max(abs(loc[i].first - loc[j].first),
                                 abs(loc[i].second - loc[j].second));

        // dp
        // init
        pts--; // #pts is the starting point
        int dp[pts][(1 << pts)];
        for (int i = 0; i < pts; i++) {
            fill(dp[i], dp[i] + (1 << pts), oo);
            dp[i][1 << i] = dist[i][pts];
        }
        for (int j = 0; j < (1 << pts); j++) {
            for (int i = 0; i < pts; i++) {
                for (int k = 0; k < pts; k++) {
                    if (((j >> k) & 1) == 1 && k != i) {
                        dp[i][j] = min(dp[i][j], dp[k][j - (1 << i)] + dist[i][k]);
                    }
                }
            }
        }

        int mx = oo;
        for (int i = 0; i < pts; i++)
            mx = min(mx, dp[i][(1 << pts) - 1] + dist[pts][i]);
        printf("%d\n", mx == oo ? 0 : mx); // WA: might have no nuts
    }

    return 0;
}

Contents

AC Code