LA3725 Hie with the Pie

题意

经典问题:TSP。

给出了n个城市,求一条最短的路径,使得经过每个城市一次且仅一次,最后回到起点。

思路

状态压缩DP。分析问题可知道是一个多阶段决策过程,每个阶段“状态”包括了可以用已经走了哪些点,和当前站在哪个点,决策就是接下来走哪个点。

状态表示:dp[二进制位,表示目前已经走过那些点][最后走的点的序号] = 从起点出发走过的最短路程

答案:min{dp[走过全部点的状态][枚举各个可能的最后走的点i] + dis(i,起点)}

边界:dp[0][起点] = 0,其它都是INF

状态转移:用dp[S][i] + dis(i,j) 去尝试更新dp[S|j][j]

代码

 

UVA 10911 Forming Quiz Teams

题意

经典模型“最优配对问题”,给出了平面上若干个点,你要把牠们两两配对,使得每一对中两点距离之和最小。

思路

分析问题:我们发现,本问题可以着眼于“最后一次配对”,是一个多阶段决策。不妨考虑当最后一次选择拿i号点去和j号点去配对,得到了某种状态时可以得到的最优解。

状态表示:dp[当前状态下各个点是否已经配对][最后一次配对的点i][最后一次配对的点j]

我们发现这个状态设的太繁了,假如我们要配对a和b这两个点,那么在所有的配对状态里面都要算入a和b的距离,在所有没配对状态里都不可以算入a和b的距离,后两个维度强行决定了一组点的配对情况,然而并没有什么意义,因为后两个维度的信息已经包括进了第一个维度里,我们只要想办法让第一个维度可以表达出决策的“分阶段”特性,能够识别出最后一步是什么就可以。

于是我们重设状态:dp[当前状态下各个点是否已经配对]并且规定在每个状态中,最低位为1对应的那个点是我们最后一次操作的点。

这样有状态转移:dp[S] = min{dis(i,j) + dp[S^i^j]} 在这里S是二进制表示的状态,i,j是假定的最后一次配对的点对,其中规定i一定是S中最低位的那个点,dis表示求距离,S^i^j表示将二进制表示的状态中i,j对应的位设成零之后得到的二进制状态

代码

 

Scroll to top