解题思路(最短路程吃完所有奶酪)
老鼠从 (0,0) 出发,要把 n 个点(奶酪坐标)全部访问一遍,问最短总路程。不要求回到原点。
这就是经典的 旅行商问题 TSP(从起点出发访问所有点的最短路径),n ≤ 15,可以用 状态压缩 DP 做到 O(n^2·2^n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
状态定义
把奶酪编号 1..n,起点当作编号 0(坐标 (0,0))。
预处理所有点两两距离 dist[i][j](含 0..n)。
设:
* dp[mask][i]:从起点 0 出发,已经吃掉集合 mask 中的奶酪(mask 的第 k 位表示奶酪 k 是否吃过),并且最后停在奶酪 i(i 在 1..n)时的最短路程。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
初始化
只吃一个奶酪 i:
* dp[1<<(i-1)][i] = dist[0][i]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
状态转移
从上一个停在 j,走到 i:
* dp[mask][i] = min(dp[mask][i], dp[pmask][j] + dista[j][i]);
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
答案
全部吃完时 full = (1<<n)-1,最后可以停在任意一个奶酪点:
ans = min_{i=1..n} dp[full][i]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
输出格式
题目要求保留 2 位小数。
用 printf("%.2f\n", ans); 或 cout<<fixed<<setprecision(2)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C++ 代码