P1433 吃奶酪

DFS方法

最后一组测试超时 时间复杂度O(n!)

#include <iostream> #include <iomanip> #include <cmath> using namespace std; const int maxn = 20; struct node { double x, y; }f[maxn]; bool vis[maxn]; double dis[maxn][maxn], dis_min = 1e9; int n; void dfs(double sum, int cur, int step){ if(sum >= dis_min){ return; } if(step == n){ if(dis_min > sum) dis_min = sum; return; } for(int i = 1; i <= n; i++){ if(!vis[i]){ vis[i] = true; dfs(sum + dis[ cur ][ i ], i, step + 1); vis[i] = false; } } } void Dis(){ double d; for(int i = 1; i <= n; i++){ d = sqrt(f[ i ].x*f[ i ].x + f[ i ].y*f[ i ].y); dis[i][0] = dis[0][i] = d; } for(int i = 1; i < n; i++){ for(int j = i + 1; j <= n; j++){ d = sqrt((f[ i ].x - f[ j ].x)*(f[ i ].x - f[ j ].x) + (f[ i ].y - f[ j ].y)*(f[ i ].y - f[ j ].y)); dis[i][j] = d; dis[j][i] = d; } } } int main(){ cin >> n; for(int i = 1; i <= n; i++) cin >> f[i].x >> f[i].y; Dis(); dfs(0, 0, 0); cout << setiosflags(ios::fixed) << setprecision(2) << dis_min << endl; return 0; }

状压dp

时间复杂度O(n^2nn) 解题思路： 1、用二进制记录所有已走点位的状态（代码中使用的是K）

设 n = 3 状态有1， 2， 3，4， 5， 6， 7（二进制） 0 => 0 0 0 1 => 1 0 0 2 => 0 1 0 3 => 1 1 0 4 => 0 0 1 5 => 1 0 1 6 => 0 1 1 7 => 1 1 1 例： 3 则表示 1， 2两点已走过 7 则表示 1， 2， 3三点已走过

2、对状态k，找出两个没有走过的点 i，j。并以 i 为末尾，由dp[ j ][k - (1 << (i - 1))] 到 i ，得到dp[ i ][ k ]dp[ i ][ k ]. 状态转移方程： dp[i][k] = min(dp[i][k], dp[j][k - (1 << (i - 1))] + dis[i][j])

#include <bits/stdc++.h> using namespace std; const int maxn = 20; double x[maxn], y[maxn]; int n; double dis[maxn][maxn]; double dp[maxn][1 << 15 + 5], dis_min = 1e9; void Dis_(){ double d; for(int i = 0; i < n; ++i){ for(int j = i + 1; j <= n; ++j){ d = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j])); dis[i][j] = dis[j][i] = d; } } } int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> x[i] >> y[i]; } Dis_(); for(int i = 1; i <= n; i++){ for(int j = 1; j < (1 << n) + 9; j++){ dp[i][j] = 1e9; } } for(int i = 1; i <= n; i++){ dp[i][1 << (i - 1)] = dis[0][i]; } for(int k = 1; k < (1 << n); ++k) { //处理所有可能的点位状态 for(int i = 1; i <= n; ++i) { //下一个需要走到的点 if((k & (1 << (i - 1))) == 0) continue; //在k，若i已经走过，则不返回 for(int j = 1; j <= n; ++j) { if(i == j) continue; //i j 不能相等 if((k & (1 << (j - 1))) == 0) continue; dp[i][k] = min(dp[i][k], dp[j][k - (1 << (i - 1))] + dis[i][j]); } } } for(int i = 1; i <= n; i++){ dis_min = min(dis_min, dp[i][(1 << n)- 1]); } cout << setiosflags(ios::fixed) << setprecision(2); cout << dis_min << endl; return 0; }