P1433 吃奶酪

#include <iostream>
#include <cmath>
using namespace std;
#define M 15
#define S(n) ((n) * (n))
double indx[M + 5], indy[M + 5], ans = 0, sum = 0;//坐标数组，从下标为1开始记录
int n, vis[M + 5] = { 0 };//vis数组，选过的数字标记为1，没选过的数字标记为0
double dis(int i, int j) {return sqrt(S(indx[i] - indx[j]) + S(indy[i] - indy[j]));
}
//c表示当前已经选了c个数字
//k表示最后一次选的是第k个点
void fun(int c, int k) {if (c == n) {if (!ans || ans > sum) ans = sum;return;}for (int i = 1; i <= n; i++) {if (vis[i]) continue;vis[i] = 1;sum += dis(i, k);fun(c + 1, i);vis[i] = 0;sum -= dis(i, k);}return;
}
int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> indx[i] >> indy[i];}fun(0, 0);printf("%.2lf", ans);return 0;
}

 8组超时，优化

#include <iostream>
#include <cmath>
using namespace std;
#define M 15
#define S(n) ((n) * (n))
double indx[M + 5], indy[M + 5], dp[70000][M + 5] = { 0 }, ans = 0; //坐标数组，从下标为1开始记录
//dp[i][j]：选择内容为i，最后一次选择的数字为j，的路径总长度
int n, vis[M + 5] = { 0 }; //vis数组，选过的数字标记为1，没选过的数字标记为0
double dis(int i, int j) { //返回第i个点到第j个点的距离return sqrt(S(indx[i] - indx[j]) + S(indy[i] - indy[j]));
}
//c表示当前已经选了c个数字
//k表示最后一次选的是第k个点
//m的二进制代表选择的内容
//sum表示这c个数字当前方案的路径总长度
void fun(int c, int k, int m, double sum) {if (c == n) {ans = sum;return;}dp[m][k] = sum; //到达一个新的节点，第一步就更新以m为内容，k为末端的路径长度for (int i = 1; i <= n; i++) {if (vis[i]) continue;int a = m + pow(2, i); //m如果自增，递归回来又要减，太麻烦，定义一个adouble d = dis(i, k); //后面最多用到三次，算出来方便用//以a为内容、i为路径已经被遍历过了，且之前的值小于等于这次遍历过去的值，那就不遍历过去了if (dp[a][i] != 0 && dp[a][i] <= sum + d) continue;//ans不为0且这次遍历过去sum超过ans，那就没必要过去了if (ans && ans <= sum + d) continue;vis[i] = 1;fun(c + 1, i, a, sum + d);vis[i] = 0;}return;
}
int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> indx[i] >> indy[i];}fun(0, 0, 0, 0);printf("%.2lf", ans);return 0;
}