听说此题做不出深搜就还没到功夫QAQ

说的可能就是我

这一题乍一看是dp(可以用dp做,但是是数位dp……),还是好好想想DFS怎么做叭,嘤~

HDU1584 蜘蛛牌(DFS)

题目链接<–点这里

蜘蛛牌是windows xp操作系统自带的一款纸牌游戏,游戏规则是这样的:只能将牌拖到比她大一的牌上面(A最小,K最大),如果拖动的牌上有按顺序排好的牌时,那么这些牌也跟着一起移动,游戏的目的是将所有的牌按同一花色从小到大排好,为了简单起见,我们的游戏只有同一花色的10张牌,从A到10,且随机的在一行上展开,编号从1到10,把第i号上的牌移到第j号牌上,移动距离为abs(i-j),现在你要做的是求出完成游戏的最小移动距离。

Input

第一个输入数据是T,表示数据的组数。

每组数据有一行,10个输入数据,数据的范围是[1,10],分别表示A到10,我们保证每组数据都是合法的。

Output

对应每组数据输出最小移动距离。

Sample Input

1

1 2 3 4 5 6 7 8 9 10

Sample Output

9

我觉得这位巨巨讲的很好,可戳

如果我来讲的话,这道题的关键点和所有DFS一样,就是有个递归过程。那么我们脑动模拟蜘蛛纸牌过程,可以发现这个递归关键点在于要不要先把第i张牌移动到比它大1的数字下方。

需要注意的是,比它大1的数字不一定在一开始的位置,所以需要用一个vis[]数组标记每张牌是否被移动。因为每张牌只能放在比它大1的牌下方,所以如果某张牌被标记为移动,只需要从这张牌往后遍历第一张没有被移动的牌,就是一开始那张牌现在所在的位置。

整个dfs过程我们需要两个变量,num代表已经排好的牌数量,sum代表当前距离和。优化剪枝的地方在于,如果sum>ans(之前搜索到的最小完整sum值),可以直接return,因为这一定不是最优解。边界条件就是当num==9时,说明我们移动了9张牌,整个蜘蛛纸牌已经有序,需要return,把sum值赋给ans(因为没有被剪枝,所以此时sum一定 < ans,为当前搜索到的最优解。

代码如下:

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
#include<bits/stdc++.h>
using namespace std;

int a[15],vis[15],ans;

void dfs(int num,int sum)
{
if(sum>ans)
return ;
if(num==9)
{
ans=sum;
return;
}
else
{
for(int i=1;i<=10;i++)
{
if(!vis[i])
{
vis[i]=1;
for(int j=i+1;j<=10;j++)
{
if(!vis[j])
{
dfs(num+1,sum+abs(a[i]-a[j]));
break;
}
}
vis[i]=0; //回溯,dfs的关键
}
}
}
}

int main()
{
int t;
cin>>t;
while(t--)
{
for(int i=1;i<=10;i++)
{
int x;
cin>>x;
a[x]=i;
}
ans=1000000;
dfs(0,0);
cout<<ans<<endl;
}
return 0;
}

最后更新: 2019年04月02日 19:38

原始链接: http://yisin.top/2019/04/02/HDU1584-蜘蛛牌(DFS)/

× 请我吃糖~
打赏二维码