$bzoj1019-SHOI2008$ 汉诺塔 $dp$

时间：2023-03-10 07:24:41
$bzoj1019-SHOI2008$ 汉诺塔 $dp$

  • 题面描述

    • 汉诺塔由三根柱子（分别用\(A\ B\ C\)表示）和\(n\)个大小互不相同的空心盘子组成。一开始\(n\)个盘子都摞在柱子\(A\)上，大的在下面，小的在上面，形成了一个塔状的锥形体。

      $bzoj1019-SHOI2008$ 汉诺塔 $dp$

      对汉诺塔的一次合法的操作是指：从一根柱子的最上层拿一个盘子放到另一根柱子的最上层，同时要保证被移动的盘子一定放在比它更大的盘子上面（如果移动到空柱子上就不需要满足这个要求）。我们可以用两个字母来描述一次操作：第一个字母代表起始柱子，第二个字母代表目标柱子。例如，\(AB\)就是把柱子\(A\)最上面的那个盘子移到柱子\(B\)。汉诺塔的游戏目标是将所有的盘子从柱子\(A\)移动到柱子\(B\)或柱子\(C\)上面。有一种非常简洁而经典的策略可以帮助我们完成这个游戏。首先，在任何操作执行之前，我们以任意的次序为六种操作\((AB,AC,BA,BC,CA,CB)\)赋予不同的优先级，然后，我们总是选择符合以下两个条件的操作来移动盘子，直到所有的盘子都从柱子\(A\)移动到另一根柱子：

      • 这种操作是所有合法操作中优先级最高的；

      • 这种操作所要移动的盘子不是上一次操作所移动的那个盘子。

      可以证明，上述策略一定能完成汉诺塔游戏。现在你的任务就是假设给定了每种操作的优先级，计算按照上述策略操作汉诺塔移动所需要的步骤数。

  • 输入格式

    • 输入有两行。第一行为一个整数\(n\ (1\leq n\leq 30)\)，代表盘子的个数。第二行是一串大写的\(ABC\)字符，代表六种操作的优先级，靠前的操作具有较高的优先级。每种操作都由一个空格隔开。

  • 输出格式

    • 只需输出一个数，这个数表示移动的次数，保证答案\(\leq 10^{18}\)

  • 题解

    • 首先当所有可能的操作都被赋予优先级，并且限制相邻两次操作不能移同一个对象，因此该汉诺塔的移动序列已经被固定。

    • 我们要做的就从最优化变成了合并操作序列中相同的部分，加速计算效率

    • 类比普通的汉诺塔问题，不难发现在移盘子的时候总会不时出现将\(1,.., x\)个盘子以同一个操作序列从某个地方移到某个地方。

    • 令三根柱子分别叫\(x,y,z\)

    • 是这个启发，我们可以设计出如下状态：

      • \(f[i][x][y]\)表示\(1,..,i\)个盘子从\(x\)移到\(y\)所需的步数
      • 特别的，当\(f[i][x][y]==-1\)时表示\(1,..,i\)个盘子从\(x\)移到\(y\)不合法

    • 这样我们可以写出转移方程

      • \[f_{i,x,y}=f_{i-1,x,y}+1+f_{i-1,y,x}+1+f_{i-1,x,y}\\
        或\\
        f_{i,x,y}=f_{i-1,x,z}+1+f_{i-1,z,y}
        \]

      • 注意到当\(1,..,i-1\)个盘子没有移完的时候，我们是不可能去移第\(i\)个盘子的

        • 分两种情况
          • 一，还有一些盘子在第\(i\)个盘子上，那我们不可能移动第\(i\)个盘子
          • 二，第\(i\)个盘子上已经没有盘子了，又分两种情况
            • \(1,..,i-1\)个盘子在同一根柱子，那么这时候我们称这\(i-1\)个盘子已经移好了，与假设不符
            • \(1,..,i-1\)个盘子不在同一根柱子，那么我们不能移第\(i\)个盘子，因为如果能够移动第\(i\)个盘子，移动到的柱子上已没有比\(i\)小的盘子，但此时两根柱子都有\(1,..,i-1\)中的某一些盘子

      • 也就是说，我们必须把\(1,..,i-1\)个盘子移好再移第\(i\)个盘子

      • 故第一个递推方程表示

        • 当\(1,..,i-1\)个盘子从\(x\)移到\(y\)合法，且\(1,..,i-1\)个盘子从\(y\)移到\(x\)合法时，
          • 我们先将\(1,..,i-1\)个盘子从\(x\)移到\(y\)，花费\(f_{i-1,x,y}\)步。
          • 因为相邻两次操作对象不能相同，我们只能将第\(i\)个盘子从\(x\)移到\(z\)，花费\(1​\)步。
          • 因为相邻两次操作对象不能相同，我们只能移\(1,..,i-1\)盘子，同时我们不能把这\(1,..,i-1\)盘子移到第\(i\)个盘子所在的\(z\)柱子，因为如此一来，我们在下一步又只能移\(1,..,i-1\)盘子，这是不合法的。因此我们只能把\(1,..,i-1\)盘子移到\(x\)柱子，花费\(f_{i-1,y,x}\)步
          • 因为相邻两次操作对象不能相同，我们只能将第\(i\)个盘子从\(x\)移到\(y\)，花费\(1\)步。
          • 最后我们将\(1,..,i-1\)移回\(y\)，花费\(f_{i-1,x,y}\)步

      • 第二个递推方程表示

        • 当\(1,..,i-1\)盘子从\(x\)移到\(z\)合法，且\(1,..,i-1\)盘子从\(z\)移到\(y\)；合法时，
          • 我们将\(1,..,i-1\)盘子从\(x\)移到\(z\)，花费\(f_{i-1,x,z}\)步
          • 因为相邻两次操作对象不能相同，我们只能将第\(i\)个盘子从\(x\)移到\(y\)，花费\(1\)步。
          • 最后我们将\(1,..,i-1\)盘子从\(z\)移回\(y\)，花费\(f_{i-1,z,y}\)步

    • 同时因为操作的优先级，我们不难发现这两个递推是不可能同时成立，但有可能同时不成立。因此当这两个递推式同时不成立时\(f_{i,x,y}=-1\)

    • 关于边界条件，根据题目给出的操作优先级确定

      • 例如：从\(x\)向其他柱子移动的操作优先级为\(xy>xz\)，因此\(f_{1,x,y}=1,f_{1,x,z}=-1\)

    • 如此递推即可

    • 网上好多博客一本正经地说了一个奇怪的\(dp\)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=55;

typedef long long ll;

ll f[MAXN][4][4];

int n;

char s[10][4];

int main(){

	scanf("%d",&n);

	for (int i=1;i<=6;i++) scanf("%s",s[i]);

	for (int i=0;i<3;i++){

		f[1][i][0]=f[1][i][1]=f[1][i][2]=-1;

		for (int j=1;j<=6;j++){

			if (s[j][0]-'A'==i){

				int to=s[j][1]-'A';

				f[1][i][to]=1;

				break;

			}

		}

	}

	for (int i=2;i<=n;i++){

		for (int j=0;j<3;j++){

			for (int k=0;k<3;k++){

				int l=3-j-k;

				f[i][j][k]=-1;

				if (f[i-1][j][k]!=-1&&f[i-1][k][j]!=-1){

					f[i][j][k]=f[i-1][j][k]*2+2+f[i-1][k][j];

				}

				if (f[i-1][j][l]!=-1&&f[i-1][l][k]!=-1){

					f[i][j][k]=f[i-1][j][l]+1+f[i-1][l][k];

				}

//				cout<<i<<" "<<j<<" "<<k<<" "<<f[i][j][k]<<endl;

			}

		}

	}

	if (f[n][0][1]!=-1) printf("%lld\n",f[n][0][1]);

	else printf("%lld\n",f[n][0][2]);

	return 0;

}

随机推荐

  1. [GO]tcp网络通信和实现

    服务端的代码 package main import ( "net" "fmt" ) func main() { //监听 listener, err := n ...

  2. [GO]非结构体匿名字段

    package main import ( "fmt" ) type mystr string //给一个类型重命名 type Person struct { name strin ...

  3. JSTL 引入

    首先要明白jstl有如下版本:  jstl1.0的引入方式为: <taglib uri="http://java.sun.com/jstl/core" prefix=&quo ...

  4. Word2010如何编辑好了直接发布****博文？

    目前大部分的博客作者在写博客这件事情上都会遇到以下3个痛点:1.所有博客平台关闭了文档发布接口,用户无法使用Word,Windows Live Writer等工具来发布博客.2.发布到博客或公众号平台 ...

  5. MATLAB搬移到别的电脑出现License Manager Error -9

    是注册码的问题,不需要重装,主要是以前的安装包不见了.解决办法: 下一个KeyGen的MLMCrypt.exe文件.运行之后在当前目录下出现一个LICENSE.DAT文件. 复制到matlab.exe ...

  6. jenkins构建后接受者收不到邮件问题解决方案

    jenkins部署.安装增强版邮件插件,配置邮件及增强版邮件通知请参考网上教程,由于教程比较多页通俗易懂,笔者在这里不做重复说明,本文重点是解决配置好增强版邮件,job构建后仍然收不到邮件的问题 步骤 ...

  7. JavaScript - this详解 （二）

    用栗子说this Bug年年有,今年特别多 对于JavaScript这么灵活的语言来说,少了this怎么活! function 函数 this 对于没有实例化的function,我们称之为函数,即没有 ...

  8. 关于webRTC

    webRTC是浏览器实现的,用来实现p2p实时通讯的协议 现在已经被chrome和firefox支持 webRTC实现了三个API供前端开发者调用 MediaStream(或者叫getUserMedi ...

  9. Split 之特殊用法

    java中split()特殊符号"." "|" "*" "\" "]"   关于点的问题是用stri ...

  10. 菜鸟的Xamarin.Forms前行之路——windows下VS运行ios模拟器调试

    在Xamarin.Forms项目中,运行安卓模拟器是很方便的,但是想要运行IOS模拟器,相对而言是困难一点. 在参考一些资料后,发现很多是与Xamarin.studio有关的方法,尝试了许久没有成功. ...

相关文章