bc #52 div 2 B || hdoj 5418 Victor and World(tsp问题,状压dp)

比赛的时候一看,tsp么

前些天好像刚写过一个clean robot什么的

然后发现n才16,而m很大..

应该有很多重复的.

那么我们取油费最少的.

然后先做一遍 floyd

之后我写了一个dfs…TLE 了…sad

正解是状压dp

虽然没写过状压dp

但是之前写过一道状态压缩的bfs

所以理解起来没有问题.

这道题的做法是: 

用dp[i][j]表示当前访问国家的状态为s,要访问的国家为j的时候的最小费用.i是二进制,i的第p位为1表示第p个国家已经访问过了,否则表示没有访问过.

那么状态转移方程则为:dp[i|(1<

初始化的时候d[i][i] =0,其他为inf

dp[0][0] 表示要访问第一个国家且没有访问国人国家的时候的状态,此时花费为0

然后先枚举访问国家的状态,再枚举访问的国家.

poj 2688 Cleaning Robot (tsp问题)

______

好蠢,竟然没看出来这道题的不同之处,以为就是个搜

然后样例什么的都过了...

结果显然wa…

然后才发现,这道题应该是tsp问题.

解法是先跑一遍bfs,

对于所有的脏点和起点,得到没两个点之间的距离.

然后跑一遍dfs,枚举出所有的组合,同时更新答案.

晚安.