Zhao70's Blog

HDU1584

发表于 | 分类于

题目大意

给定值为1到10的纸牌的顺序，每张牌只能放在大一的纸牌上，每次移动的代价为两张牌的差值的绝对值， 求最小代价。

题目思路

在不改变数组排列顺序的前提下生成全排列的题，当然还要带上剪枝和关于回溯的判断， 真的是考察dfs的好题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cmath>
using namespace std;
int loc[11];
int isUsed[11];
int ans;
void dfs(int step, int temp)
{
    //剪枝. 无论何时, 只要当前步数大于已知的ans(最大值), 就进行回溯
    if(ans < temp)
        return;
    //由于值为10的牌的特殊性, 不需要进行移动, 所以步数为9步即可得出结论
    if(step == 9)
    {
        if(ans >= temp)
            ans = temp;
        return;
    }
    //选择进行九张牌的移动, 移动九次
    //在第几层递归, 此循环就选择i当作, 该层的一个子树的根节点
    for(int i = 1; i < 10; i++)
    {
        if(isUsed[i])
            continue;
        //选择移动到第几张牌的下面
        for(int j = i + 1; j <= 10; j++)
        {
            //比如要移1了，如果2,3,4,5都已经被移动过了 那么这几张牌必定叠放在6的下面，所以要移到6的位置
            if(isUsed[j])
                continue;
            isUsed[i] = true;
            dfs(step + 1, temp + abs(loc[i] - loc[j]));
            isUsed[i] = false;
            //注意不要再这个地方回溯 如果回溯了 就像是又一个全排列 而且牌得移动不合理，比如2移到6了，结果回溯就直接跳过3~6到了7的下面(比如: temp的值比ans更大, 但说不定2 -> 6的移动是合法的, 但之后存在不合法的移动)
            break;
        }
    }
}
int main()
{
    int nTest;
    cin >> nTest;
    while(nTest--)
    {
        for(int i = 1; i <= 10; i++)
        {
            int val;
            cin >> val;
            //怎么存储数据也是有讲究的
            loc[val] = i;
            isUsed[i] = false;
        }
        ans = 9999999;
        dfs(0, 0);
        cout << ans << endl;
    }
    return 0;
}

参考链接

hdu1584 蜘蛛牌（经典dfs）
hdu 1584 蜘蛛牌