HDU - 1584 蜘蛛牌(dfs+最优性剪枝)

题目链接：点击查看

题目大意：给出10张牌，随机分布在1~10十个不同的位置，要求模拟蜘蛛纸牌的游戏规则，问移动的最短距离之和是多少

题目分析：我们可以直接dfs搜索，但需要想清楚该怎么搜索，这个题目有点贪心的思想，因为要求移动距离之和最小，所以我们应该尽量避免多余的移动，简单来说，我们只需要将当前牌放置到比当前牌序号大1的牌上就行，说起来可能有些抽象，举个例子，牌1只需要移动到牌2上即可，不需要移动到牌3上然后再移动到牌2上之类的，相对的，牌10的位置就固定了，因为牌10在哪里都一样。

然后就是搜索了，因为不一定是按照顺序来的，不一定是牌1放到牌2上，然后牌2带着牌1放到牌3上，也可能是牌2先放到牌3上，然后牌1再放到牌2上等等等等，所以我们在搜索时，第一层for需要枚举所当前轮次所需要移动的牌，然后第二层for需要寻找比当前牌序号大1的牌的位置，然后放上去即可，一开始我就是不太会处理第二层for循环，以为单纯的用i+1来判断就行，果不其然的WA了一发，其实可以换个思想，比如我们已经将牌4放到牌5上了，那么我们接下来需要将牌3放到牌4上，我们该处理的距离肯定不是abs(a[3]-a[4])了，因为此时的牌4已经到了牌5的位置，所以正确距离应该是abs(a[3]-a[5])才对，所以我们的vis数组保存的是每一堆扑克中最底层的那个牌的大小，并且根据规则，我们可以保证这个牌的序号一定是该堆牌中最大的一张，所以我们在寻找目标牌的位置时，只需要在i+1-10中找到第一个在最底层的数即可，假设我们找到的目标牌是k，则可以保证第i+1~k张牌已经放到了第k张牌的上面

emmm，可能理解起来有点麻烦，但毕竟也是我想了有一个小时才想明白的问题。。直接挂代码吧，和网上绝大部分的代码一样：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=15;int a[N];int ans;bool vis[N];void dfs(int pos,int cnt) {if(cnt>=ans)//最优性剪枝return;if(pos==9)//若所有牌的情况都处理完毕，更新结果{ans=cnt;return;}for(int i=1;i<10;i++)//选择需要移动的牌{if(!vis[i]){vis[i]=true;for(int j=i+1;j<=10;j++)//找目标牌的位置if(!vis[j]){dfs(pos+1,cnt+abs(a[i]-a[j]));break;}vis[i]=false;}} }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){for(int i=1;i<=10;i++){int num;scanf("%d",&num);a[num]=i;}memset(vis,false,sizeof(vis));ans=100;//答案初始化为100，其实到90就行，强迫症凑个整dfs(0,0);printf("%d\n",ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU - 1584 蜘蛛牌(dfs+最优性剪枝)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。