洛谷P1433 吃乳酪

題目連結https://www.luogu.com.cn/problem/P1433

解決思路

總共只有16個點，只需要窮舉所有情況即可。

窮舉過程中會出現很多重複的情況，所以需要儲存每一種狀態的結果，並在碰到相同情況時直接使用儲存的結果。

使用一個16位元的資料型別例如unsigned short即可表示16塊乳酪是否已經被撿起。

C++程式碼如下：

#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>

struct Pos {
    double x;
    double y;
};

Pos arr[16];
double saved_dis[16][16];
double saved_res[16][65536];
int n;

inline double distance(int i, int j) {
    if (saved_dis[i][j]) {
        return saved_dis[i][j];
    };

    const Pos& src = arr[i];
    const Pos& des = arr[j];
    saved_dis[i][j] = std::sqrt((src.x - des.x) * (src.x - des.x) + (src.y - des.y) * (src.y - des.y));
    return saved_dis[i][j];
}

inline unsigned short set(unsigned short points, int i) {
    return points | (1 << i);
}

inline unsigned short reset(unsigned short points, int i) {
    return points & ~(1 << i);
}

inline bool test(unsigned short points, int i) {
    return points & (1 << i);
}

// 求：從點arr[curPoxI]出發，剩餘的點為points，距離最短的結果
double resolve(int curPosI, unsigned short points) {
    if (points == 0) {
        return 0;
    }

    if (saved_res[curPosI][points]) {
        return saved_res[curPosI][points];
    }

    double ret = std::numeric_limits<double>::max();

    for (int i = 1; i <= n; i++) {
        if (test(points, i)) {
            ret = std::min(distance(curPosI, i) + resolve(i, reset(points, i)), ret);
        }
    }

    saved_res[curPosI][points] = ret;
    return ret;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin >> n;
    Pos start = {0, 0};
    arr[0] = start;

    unsigned short points = 0;
    for (int i = 1; i <= n; i++) {
        std::cin >> arr[i].x >> arr[i].y;
        points = set(points, i);
    }

    std::cout.setf(std::ios_base::fixed);
    std::cout.precision(2);
    std::cout << resolve(0, points) << "\n";
}