本文主要是介绍【2016-2017 ACM-ICPC (ECNA 2016) G】That's One Hanoi-ed Teacher(思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/gym/101196
题目大意：询问当前状态是否是最优方案中的一种，若是输出剩下还需多少步
题目思路：
汉诺塔的递归函数的写法是
dfs(a,c,b)
dfs(b,a,c)
分别是在a以c为辅助去b，在b以a为辅助去c
所以其实它呈现出的是一个二叉树的结构
首先根据汉诺塔的性质，最大的环要么在第一个柱子，要么在第三个柱子，如果在第二个柱子就说明这种方案不是最优方案
现在问题可以转换成它在二叉树的哪一个位置
如果是在左边那个状态的话，就说明右边那一个状态中的所有情况一定都还没有经历，都属于剩下要走的步数，那就加上这个状态中的所有步数，就是2^n种(n表示这个状态中的环的个数)，然后继续递归这个状态寻找次大的情况，如果是右边那个状态，那啥也不知道，继续递归到次大的情况，由此就能获得所有的情况
以下是代码：
#include<bits/stdc++.h>using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
int n,x,z[105],flag;
ll ans;
void dfs(int a,int b,int c,int n){if(!n)return;if(z[n]==a){ans+=1ll<<(n-1);dfs(a,c,b,n-1);}else if(z[n]==c){dfs(b,a,c,n-1);}else flag=1;
}
int main()
{while(~scanf("%d",&n)){int num=n;rep(i,1,n)scanf("%d",&x),z[x]=1;scanf("%d",&n);num+=n;rep(i,1,n)scanf("%d",&x),z[x]=2;scanf("%d",&n);num+=n;rep(i,1,n)scanf("%d",&x),z[x]=3;ans=flag=0;dfs(1,2,3,num);if(flag){printf("No\n");continue;}printf("%I64d\n",ans);}return 0;
}
这篇关于【2016-2017 ACM-ICPC (ECNA 2016) G】That's One Hanoi-ed Teacher(思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
