P1433. 吃奶酪

考点

• 状态压缩动态规划

题解

见思路

思路

一开始以为是贪心，但很容易举个反例：如果有多个距离一样的奶酪，该走哪个确保整体最优呢？

很明显也不是单纯的DFS或BFS：

• 最大有15个奶酪，也就是说纯粹用DFS高达15的阶乘...再怎么剪枝也会炸
• 也不是BFS，BFS是找步骤最低的解...这里要找解里面总距离最小的

那只有DP一种可能了

---

微观上看，每个合法的序列都可以拆分成子序列+结尾元素，比如序列{1, 2, 3, 4, 5} = {1, 2, 3, 4} + {5}

最多只有15个元素，而int有32位，所以可以将子序列映射为整数，以状态压缩来达成DP

内存限制是10⁶数量级，故而状态压缩不能超过2²⁰这一极限

这样并不能保存元素的前后顺序，所以每次只保存，相同组成的序列中总距离最小的

递推

根据上述思路，很容易写出状态转移方程： \[ \min \left( dp\left[ i \right] \left[ j \right] ,dp\left[ i\oplus (1<<(j-1)) \right] \left[ k \right] +dis\left( j,k \right) \right) \rightarrow dp\left[ i \right] \left[ j \right] \] i代表当前序列，以j结尾；而当前序列是由某个不包含j，以k结尾的子序列在末尾添加j组成的

你可能会好奇为什么是1 << (j - 1)而不是1 << j，这样不是占了最低位属于起点的位置吗？

因为起点必须包含在序列且只能出现在开头，边界值初始化时可以一次性处理

如果把最低位空着，会导致部分状态转移遇到跳过起点的情况导致报错

我调了10多个小时带来的教训

#include <bits/stdc++.h>
using namespace std;
const int LEN = 16;
int N;
double ans = INT_MAX, table[LEN][LEN], dp[1 << LEN][LEN];

struct Node
{
    double x_, y_;
    Node(double x = 0, double y = 0) : x_(x), y_(y) {}
} arr[LEN];

double dis(Node &a, Node &b)
{
    double x1 = a.x_, y1 = a.y_, x2 = b.x_, y2 = b.y_;
    return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
}

void init()
{
    //提前打表，两点之间的距离
    for (int i = 0; i <= N - 1; ++i)
        for (int j = i + 1; j <= N; ++j)
            table[i][j] = table[j][i] = dis(arr[i], arr[j]);
    //初始化最大值
    memset(dp, 127, sizeof(dp));
    //由于不能自己跳自己
    //所以令序列只有自己的情况下，等同于从起点跳到当前点
    dp[0][0] = 0;
    for (int i = 1; i <= N; ++i)
        dp[1 << (i - 1)][i] = table[0][i];
}

int main()
{
    cin >> N;
    for (int i = 1; i <= N; ++i)
        cin >> arr[i].x_ >> arr[i].y_;
    init();
    for (int i = 1; i < (1 << N); ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            //序列里如果不包含结尾元素，那肯定是伪序列呐
            if (i & (1 << (j - 1)) == 0)
                continue;
            for (int k = 1; k <= N; ++k)
            {
                //不能自己跳自己
                if (k == j)
                    continue;
                dp[i][j] = min(dp[i][j], dp[i ^ (1 << (j - 1))][k] + table[j][k]);
            }
        }
    }
    for (int i = 1; i <= N; ++i)
    {
        ans = min(ans, dp[(1 << N) - 1][i]);
    }
    cout << fixed << setprecision(2) << ans;
    return 0;
}

记忆化搜索

如果用递归实现，就方便很多了....因为能直接记录上个序列及其结尾元素

每次判断应该添加什么元素到上次序列的末尾：

• 如果之前有记录本次前后搭配

  若之前的搭配值更小，保留原有的

  若之前的搭配值更大，用当前搭配更新

• 若无记录，记录本次搭配

#include <bits/stdc++.h>
using namespace std;
const int LEN = 16;
int N, vis[LEN];
double ans = INT_MAX, table[LEN][LEN], mem[1 << LEN][LEN];

struct Node
{
    double x_, y_;
    Node(double x = 0, double y = 0) : x_(x), y_(y) {}
} arr[LEN];

double dis(Node &a, Node &b)
{
    double x1 = a.x_, y1 = a.y_, x2 = b.x_, y2 = b.y_;
    return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
}

void init()
{
    //提前打表，两点之间的距离
    for (int i = 0; i <= N - 1; ++i)
        for (int j = i + 1; j <= N; ++j)
            table[i][j] = table[j][i] = dis(arr[i], arr[j]);
}

//pre：上次序列的最后一位，因为状态压缩导致顺序混乱，所以要单独记录
//qe：上次序列
//sum：上次总距离
//cnt：计数
void dfs(int pre, int qe, double sum, int cnt)
{
    //如果过程中总和已经大于答案，剪枝
    if (sum >= ans)
        return;
    //统计答案
    if (cnt > N)
    {
        ans = min(ans, sum);
        return;
    }
    //0点必须为序列第一个，所以从1开始遍历
    for (int i = 1; i <= N; ++i)
    {
        if (vis[i])
            continue;
        double nxt_sum = sum + table[pre][i];
        //之前该情况出现过，且之前的值更小
        //那当然本次要剪枝了，因为我们只保留最小值
        if (mem[qe][i] && mem[qe][i] <= nxt_sum)
            continue;
        vis[i] = 1;
        mem[qe][i] = nxt_sum;
        dfs(i, qe | (1 << (i - 1)), nxt_sum, cnt + 1);
        vis[i] = 0;
    }
}

int main()
{
    cin >> N;
    for (int i = 1; i <= N; ++i)
        cin >> arr[i].x_ >> arr[i].y_;
    init();
    dfs(0, 0, 0, 1);
    cout << fixed << setprecision(2) << ans;
    return 0;
}