首页 > 代码库 > 洛谷P1573 栈的操作 [2017年6月计划 数论11]
洛谷P1573 栈的操作 [2017年6月计划 数论11]
P1573 栈的操作
题目描述
现在有四个栈，其中前三个为空，第四个栈从栈顶到栈底分别为1,2,3,…,n。每一个栈只支持一种操作：弹出并 压入。它指的是把其中一个栈A的栈顶元素x弹出，并马上压入任意一个栈B中。但是这样的操作必须符合一定的规则才能进行。规则1：A栈不能为空。规则 2：B栈为空或x比B栈栈顶要小。
对于给定的n，请你求出把第四个栈的n个元素全部移到第一个栈的最少操作次数。
由于最少操作次数可能很多，请你把答案对1000007取模。
输入输出格式
输入格式：一行，一个n
输出格式：一行，一个正整数，为把最少操作次数 mod 1000007的值
输入输出样例
输入样例#1：
2
输出样例#1：
3
说明
对于30%的数据，n<=8
对于60%的数据，n<=60
对于100%的数据，n<=2*10^9
四根柱子的汉诺塔问题。
f3[i]表示三根汉诺塔柱子，有i个盘子的操作数
f4[i]表示四跟汉诺塔柱子，有i个盘子的操作数
可得：f4[i] = 2f4[j] + f3[i - j],1 <= i < j <= n
可以这样理解：先把j个盘子放到第三根柱子上，操作数f4[j],然后把剩余的i - j个盘子通过三根柱子放到第四根柱子上，方案数f3[i - j ]，
然后把j个盘子通过四根柱子放到第四个盘子上
打表出来发现他们的差值有规律：
1 2 2 4 4 4 8 8 8 8 16 16 16 16 16 32 32 32 32 32 32.....
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 #include <queue> 8 inline void read(long long &x){x = 0;char ch = getchar();char c = ch;while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();while(ch >= ‘0‘ && ch <= ‘9‘)x = x * 10 + ch - ‘0‘, ch = getchar();} 9 inline int max(int a, int b){return a > b ? a : b;}10 inline int min(int a, int b){return a < b ? a : b;}11 inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}12 13 const int INF = 0x3f3f3f3f;14 const int MOD = 1000007;15 long long n;16 long long base = 1, k = 1, m = 1;17 long long ans = 0;18 19 int main()20 {21 read(n);22 long long k = 1;23 long long i;24 for(;k <= n;n -= k, ++k)25 {26 ans += (k * (base % MOD)) % MOD;27 ans %= MOD;28 base <<= 1;29 base %= MOD;30 }31 printf("%lld", (ans + (((n % MOD) * (base % MOD)) % MOD)) % MOD);32 return 0;33 }
洛谷P1573 栈的操作 [2017年6月计划 数论11]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。