吃奶酪

状压DP

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int N = 20;
int n;
bool vis[N];
double ans = 1e9, dp[2<<15][20];      //dp用来存路径
struct node {
  double x;
  double y;
}a[N];

double discal (int l, int m) {               //距离计算函数
  return sqrt((a[l].x - a[m].x) * (a[l].x - a[m].x) + (a[l].y - a[m].y) * (a[l].y - a[m].y));
}

//dfs(当前吃了多少个，当前吃的第几个，当前跑了多远，现在的点)
void dfs(int sum, int nowi, double dis, int nowdot) {
  if (dis > ans) {                          //剪枝：超过历史最近距离舍去
    return;
  }
  if (sum == n) {
    if (dis < ans) ans = dis;               //比较，留下最优数值
      return;
  }
  for (int i = 1; i <= n; i++) {            //正序逐个尝试
    if (!vis[i]) {
      int p = nowdot + (1 << (i - 1));      //用二进制记录状态
      //二进制状态压缩从当前点到这个点
      if (dp[p][i] != 0 && dp[p][i] <= dis + discal(nowi, i)) { //剪枝：如果从p到i的距离已经有过更新并且本次构造的距离还大于之前，则跳过
        continue;
      }
      vis[i] = true;
      dp[p][i] = dis + discal(nowi, i);     //添加或更新新的距离
      dfs(sum + 1, i, dp[p][i], p);
      vis[i] = false;
    }
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].y;
  }
  dfs(0, 0, 0, 0);
  printf("%.2lf", ans);
  return 0;
}

笔记：用二进制压缩保存记录点节省很大一部分空间，剪枝排除不合法的方案，使总方案数（二进制储存）大大减少从而减少枚举，但是一个变量的记录点要控制在64个以内