[luoguP1433] 吃奶酪（DP || Dfs）

深搜加剪纸可A（O(玄学) 1274ms）

——代码

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <iostream>
 4 
 5 int n;
 6 double ans = ~(1 << 31), a[16], b[16];
 7 bool vis[16];
 8 
 9 inline double min(double x, double y)
10 {
11     return x < y ? x : y;
12 }
13 
14 inline double query(int x, int y)
15 {
16     return sqrt((a[x] - a[y]) * (a[x] - a[y]) + (b[x] - b[y]) * (b[x] - b[y]));
17 }
18 
19 inline void dfs(int now, double sum, int k)
20 {
21     if(k == n + 1)
22     {
23         ans = min(ans, sum);
24         return;
25     }
26     if(sum > ans) return;
27     for(int i = 1; i <= n; i++)
28         if(!vis[i])
29         {
30             vis[i] = 1;
31             dfs(i, sum + query(now, i), k + 1);
32             vis[i] = 0;
33         }
34 }
35 
36 int main()
37 {
38     scanf("%d", &n);
39     for(int i = 1; i <= n; i++) scanf("%lf %lf", &a[i], &b[i]);
40     dfs(0, 0, 1);
41     printf("%.2lf
", ans);
42     return 0;
43 }

View Code

然而状压DP，稳一手（据说O(n²*2ⁿ) 73ms）

采用记忆化搜索。

设f[i][S]为已经走过的点的集合为S，当前停留在点i的最短距离

f[i][S] = f[j][S - i] + dis(i, j) (i, j ∈ S && i != j)

——代码

 1 #include <cmath>
 2 #include <cstdio>
 3 
 4 const int INF = 1e9;
 5 int n;
 6 double ans, a[16], b[16], f[16][1 << 16];
 7 
 8 inline double dist(int i, int j)
 9 {
10     return sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
11 }
12 
13 inline double min(double x, double y)
14 {
15     return x < y ? x : y;
16 }
17 
18 inline int istrue(int x, int S)
19 {
20     return (1 << x - 1) & S;
21 }
22 
23 inline int set0(int x, int S)
24 {
25     return (~(1 << x - 1)) & S;
26 }
27 
28 inline void dfs(int now, int S)
29 {
30     if(f[now][S] != -1) return;
31     f[now][S] = INF;
32     for(int i = 1; i <= n; i++)
33     {
34         if(i == now) continue;
35         if(!istrue(i, S)) continue;
36         dfs(i, set0(now, S));
37         f[now][S] = min(f[now][S], f[i][set0(now, S)] + dist(i, now));
38     }
39 }
40 
41 int main()
42 {
43     int i, j;
44     scanf("%d", &n);
45     for(i = 1; i <= n; i++) scanf("%lf %lf", &a[i], &b[i]);
46     for(i = 1; i <= n; i++)
47         for(j = 1; j < (1 << n); j++)
48             f[i][j] = -1;
49     for(i = 1; i <= n; i++) f[i][1 << i - 1] = dist(0, i);
50     for(i = 1; i <= n; i++) dfs(i, (1 << n) - 1);
51     ans = INF;
52     for(i = 1; i <= n; i++) ans = min(ans, f[i][(1 << n) - 1]);
53     printf("%.2lf
", ans);
54     return 0;
55 }

View Code

用递推更简便（68ms）

——代码

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 const int INF = 1e9;
 6 int n, m;
 7 double ans, a[16], b[16], f[16][1 << 16];
 8 
 9 inline double dist(int i, int j)
10 {
11     return sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
12 }
13 
14 inline double min(double x, double y)
15 {
16     return x < y ? x : y;
17 }
18 
19 int main()
20 {
21     int i, j, S, x, y;
22     scanf("%d", &n);
23     m = (1 << n) - 1;
24     for(i = 1; i <= n; i++) scanf("%lf %lf", &a[i], &b[i]);
25     memset(f, 0x7f, sizeof(f));
26     for(i = 1; i <= n; i++) f[i][1 << i - 1] = dist(0, i);
27     for(S = 1; S <= m; S++)
28         for(i = 1; i <= n; i++)
29         {
30             if(!((1 << i - 1) & S)) continue;
31             for(j = 1; j <= n; j++)
32             {
33                 if(i == j) continue;
34                 if(!((1 << j - 1) & S)) continue;
35                 f[i][S] = min(f[i][S], f[j][(1 << i - 1) ^ S] + dist(j, i));
36             }
37         }
38     ans = INF;
39     for(i = 1; i <= n; i++) ans = min(ans, f[i][m]);
40     printf("%.2lf
", ans);
41     return 0;
42 }

View Code