首页 > 代码库 > BZOJ 1019: [SHOI2008]汉诺塔
BZOJ 1019: [SHOI2008]汉诺塔
Description
一个汉诺塔,给出了移动的优先顺序,问从A移到按照规则移到另一个柱子上的最少步数.
规则:小的在大的上面,每次不能移动上一次移动的,选择可行的优先级最高的.
Sol
DP.
倒着DP.但是他有优先级,所以他的方案是唯一的.
状态 \(f[a][i]\) 表示 将 \(a\) 柱上的 \(i\) 个移到,能移动到的柱子上的步数.
他能移动到的柱子也是唯一的,这个可以跟DP一起递推出来.
\(g[a][j]\) 表示 将 \(a\) 柱上的 \(i\) 个能移动到的柱子.
然后就开始递推了,跟普通汉诺塔一样,把 \(i-1\) 个先移走,然后移动第 \(i\) 个盘子,显然他只能移动到 \(i-1\) 移动到的另一个柱子,然后考虑把 \(i-1\) 个一回来,这时候就有问题了.. \(i-1\) 个在优先级的影响下可能会回到原位置,这时候就不能把这些一共 \(i\) 个盘子移到 \(i\) 所在的柱子了,所以只能将 \(i\) 移到 \(i-1\) 一开始移动到的那个柱子.
结果就是 \(f[1][n]\) .
时间复杂度 \(O(n)\)
Code
/************************************************************** Problem: 1019 User: BeiYu Language: C++ Result: Accepted Time:0 ms Memory:1288 kb****************************************************************/ #include<cstdio>#include<iostream>using namespace std; #define debug(a) cout<<#a<<"="<<a<<" "const int N = 35; int n,b[3];int g[3][N];long long f[3][N]; int main(){ scanf("%d",&n); for(int i=1;i<=6;i++){ char fr=getchar();while(fr>‘Z‘ || fr<‘A‘) fr=getchar(); char to=getchar();while(to>‘Z‘ || to<‘A‘) to=getchar(); if(!b[fr-‘A‘]) b[fr-‘A‘]=1,g[fr-‘A‘][1]=to-‘A‘,f[fr-‘A‘][1]=1; } for(int i=2;i<=n;i++){ for(int a=0,b,c;a<3;a++){ b=g[a][i-1],c=3-a-b; if(g[b][i-1] == c) f[a][i]=f[a][i-1]+1+f[b][i-1],g[a][i]=c; if(g[b][i-1] == a) f[a][i]=f[a][i-1]+1+f[b][i-1]+1+f[a][i-1],g[a][i]=b; } }cout<<f[0][n]<<endl; return 0;}
BZOJ 1019: [SHOI2008]汉诺塔
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。