[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 13 14 inline double query(int x, int y) 15 18 19 inline void dfs(int now, double sum, int k) 20 26 if(sum > ans) return; 27 for(int i = 1; i <= n; i++) 28 if(!vis[i]) 29 34 } 35 36 int main() 37
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 12 13 inline double min(double x, double y) 14 17 18 inline int istrue(int x, int S) 19 22 23 inline int set0(int x, int S) 24 27 28 inline void dfs(int now, int S) 29 39 } 40 41 int main() 42
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 13 14 inline double min(double x, double y) 15 18 19 int main() 20 37 } 38 ans = INF; 39 for(i = 1; i <= n; i++) ans = min(ans, f[i][m]); 40 printf("%.2lf\n", ans); 41 return 0; 42 }
View Code

上一篇：[luoguP2890] [USACO07OPEN]便宜的回文Cheapest Palindrome（DP）

下一篇：[BZOJ2120] 数颜色 &amp;&amp; [bzoj2453] 维护队列（莫队 || 分块）

---

DP dfs