uva 1414 - Hanoi Towers(dp)_JeraKrs的博客-程序员秘密

题目大意：给出n，表示说有n个碟子，有三根柱子，进行汉诺塔游戏，不过不同的是说，移动碟子必须按照给出的顺序，如果可以移动，则必须移动当前的碟子到指定位置（所谓不能移动是因为其他位置上的碟子比当前位置上的要小）；并且不能连续移动同一个碟子两次。

解题思路：因为移动顺序被限制死了，所以移动的方案是固定的，而且除了最小的碟子以外，所有碟子都会被比自己小的碟子限制住，而且如果前一次不是移动最小的碟子，那么当前一定会移动最小的碟子。并且说最小的碟子移动到哪一个柱子，就会决定说下一个碟子必须移动到哪里，没有的选，也不需要考虑顺序。

所以我们只需要考虑最小碟子的移动的顺序即可

1）A -> B/C ->C/B ->A x = 2,y=1

2) A -> B/C -> A x =3, y=2

3) A ->B/C ->C/B ->B/C x=3,y=0

然后dp[i] = dp[i-1]*x + y。

#include <stdio.h>
#include <string.h>

const int N = 50;
typedef long long ll;

int n;
ll x, y, dp[N];

inline void init () {
	int v[5];
	char s[5];
	memset(v, 0, sizeof(v));

	for (int i = 0; i < 6; i++) {
		scanf("%s", s);
		int u = s[0] - 'A' + 1;
		int k = s[1] - 'A' + 1;

		if (v[u]) continue;

		v[u] = k;
	}

	if (v[2] != 1 && v[3] != 1) {
		x = 3; y = 0;
	} else if (v[v[1]] == 1) {
		x = 3; y = 2;
	} else {
		x = 2; y = 1;
	}
}

int main () {
	while (scanf("%d", &n) == 1) {
		init ();
		dp[1] = 1;
		for (int i = 2; i <= n; i++)
			dp[i] = dp[i-1] * x + y;
		printf("%lld\n", dp[n]);
	}
	return 0;
}

本文链接：https://blog.csdn.net/u011328934/article/details/21454489

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Spark 2.2.0 集群部署_我的微信公众号的博客-程序员秘密

环境说明服务器1主机名：node201IP：10.0.0.201OS: centos 7.4hadoop: NameNode, ResourceManager, SecondaryNameNode spark: master服务器2主机名：node202IP：10.0.0.202OS: centos 7.4hadoop: DataNode,

Mxnet/Gluon学习系列（二）—— mxnet中的延迟执行_mx.nd.waitall()_TurtleMeow的博客-程序员秘密

龟龟是最可爱的小猫咪Mxnet中的延迟执行import numpy as npimport timeimport mxnet.ndarray as ndprint("===============start using mxnet ndarray============")start = time.time()x = nd.random.uniform(shape = (200...

Oracle RMAN删除归档日志脚本_Lucifer三思而后行的博客-程序员秘密

每天一个 DBA 小知识，助你更进一步！

二，建立第一个项目，跟模拟器的使用_勥小透明的博客-程序员秘密

建立第一个项目：没啥好说的，就填个项目名选上需要的API，我就选了个2.2的api这里就是package name，这里要改改，填一个自己的，我这里瞎写的，然后完成就完活了运行项目和模拟器的配置：安卓模拟器名字叫AVD打开窗口-AVD Manager弹出一个窗口，右边有个new，点了name就是填个名字target还是选需要的api，这里接着选安

FZU 2253 DP（最大子段和变形）_斗片dp2253_Bahuia的博客-程序员秘密

题意：题目链接：http://acm.fzu.edu.cn/problem.php?pid=2253 给出一串01序列，现在要选择一个区间[L,R]翻转，求得反转之后的序列包含的1最多有多少个。思路：最大子段和的变形。设dp[i]表示以位置i为反转终点最多有1的个数，那么一共只有两种可能，要么从之前的最大值转移过来，要么从i点开始翻转，并加上i-1之前的前缀和，因此可以得出方程： dp[i]

标准C＋＋类std::string的内存共享和Copy-On-Write..._weixin_33965305的博客-程序员秘密

标准C＋＋类std::string的内存共享和Copy-On-Write技术陈皓 1、概念 Scott Meyers在《More Effective C++》中举了个例子，不知你是否还记得？在你还在上学的时候，你的父母要你不要看电视，而去复习功课，于是你把自己关在房间里，做出一副正在复习功课的样子，其实你在干着别的诸如给班上的某位女生写情书之类的事，而一旦你的父母出来在你房间要检查你是否在复...