HDU 1584：蜘蛛牌（DFS）

http://acm.hdu.edu.cn/showproblem.php?pid=1584

题意：要让小的牌放到大的牌上面最少移动的距离。

思路：看成让大的牌放在小的牌上面了。。。用一个标记数组vis判断该点是否移动了。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <string>
 6 #include <cmath>
 7 #include <queue>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <stack>
12 using namespace std;
13 #define INF 0x3f3f3f3f
14 typedef long long LL;
15 int pos[15], vis[15], ans;
16 
17 void dfs(int u, int sum) {
18     if(u == 10) { // 如果9张牌都动过了,就得到答案了
19         ans = min(ans, sum); return ;
20     }
21     for(int i = 1; i <= 10; i++) {
22         if(!vis[i]) { // 如果这张牌没动过
23             vis[i] = 1; // 让他放到比它大的牌的上面
24             for(int j = i + 1; j <= 10; j++) {
25                 if(!vis[j]) { // 如果这张牌没动过,那么可以放
26                     // 相当于把i这张牌放到j这张牌上面
27                     dfs(u + 1, sum + abs(pos[j] - pos[i]));
28                     break;
29                 }
30             }
31             vis[i] = 0;
32         }
33     }
34 }
35 
36 int main() {
37     int t;
38     scanf("%d", &t);
39     while(t--) {
40         memset(vis, 0, sizeof(vis));
41         int a; ans = INF;
42         for(int i = 1; i <= 10; i++) scanf("%d", &a), pos[a] = i;
43         dfs(1, 0);
44         printf("%d
", ans);
45     }
46     return 0;
47 }