luogu_P1433

题目大意&链接

有 n 块奶酪，小老鼠从 (0, 0) 点出发，要吃掉所有奶酪，求跑过的最少距离。
输入输出：输入为奶酪数量 n 以及每块奶酪的横、纵坐标 xi, yi；输出为保留两位小数的最少跑动距离。

输入输出样例：
输入：

4
1 1
1 -1
-1 1
-1 -1

输出：

7.41

详情：luogu_P1433

解题思路

状态压缩与记忆化搜索：

1. 状态表示：使用 pos 表示当前所在奶酪的索引，deep 表示已吃奶酪的数量，len 表示已跑过的距离，path 是一个整数，通过位运算（状态压缩）记录已经访问过的奶酪（每一位代表一块奶酪是否被访问 ）。

2. 记忆化：dp[pos][path] 存储从当前状态（在 pos 号奶酪位置、已访问 path 对应奶酪集合 ）出发，吃完剩余奶酪所需的最短距离增量。避免重复计算相同状态，大幅减少递归次数。

AC代码附上

// 要吃掉所有奶酪，求跑过的最少距离
#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n; // 奶酪数量
// 存储每块奶酪的坐标，a[i][0]为横坐标，a[i][1]为纵坐标
double a[N][2];
// 标记奶酪是否被访问过，用于回溯
bool st[N];
// 记忆化数组，dp[pos][path]存储对应状态的最短距离增量
// 第 i 位为 1：表示第 i 块奶酪已经被访问过（吃过）。
// 第 i 位为 0：表示第 i 块奶酪未被访问过。
double dp[N][1 << 16]; 

// pos：当前所在奶酪的索引
// deep：已吃奶酪数量
// len：已跑过的距离
// path：哪些奶酪被吃
double dfs(int pos, int deep, double len, int path) 
{
    double ans = 1e9 + 10;
    // 递归终止条件：已吃完所有奶酪，返回已跑距离
    if(deep == n) return len;
    // 若该状态已计算过，直接返回存储的最短距离
    //（当前已跑距离 + 后续最短增量 ）
    if(dp[pos][path]) return len + dp[pos][path];
   
    // 遍历所有奶酪
    for(int i = 1; i <= n; i++)
    {
        // 跳过已访问过的奶酪
        if(st[i]) continue;
        
        // 标记当前奶酪为已访问
        st[i] = 1;
        // 计算当前奶酪与所在奶酪的欧几里得距离
        double r1 = a[i][0] - a[pos][0];
        double r2 = a[i][1] - a[pos][1];
        double r = sqrt(r1 * r1 + r2 * r2);
        // 递归访问下一块奶酪，更新最短距离
        // path | (1 << i) 将 path 中第 i 位的状态改为 1
        ans = min(ans, dfs(i, deep + 1, len + r, path | (1 << i)));
        // 回溯，取消标记
        st[i] = 0;
    }
    // 存储当前状态下，吃完剩余所有奶酪所需的最短距离
    dp[pos][path] = ans - len;
    return ans;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1];
    
    printf("%.2lf", dfs(0, 0, 0, 0));
    return 0;
}