本文主要是介绍【递推】【DP】-HDU-1996-汉诺塔⑥，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1996
题目描述：问三个柱子上放N个盘子，一共可能有多少种组合？（可以有柱子不放，放的时候依然满足下面盘子比上面盘子大）
解题思路：
对于放N个盘子，ans [ N ] = 3 + 6 * f ( N ) +6 * g ( N )
这三项依次代表这N个盘子分成一堆，两堆，三堆时有多少种可能。排列组合什么的不多解释、
f 函数代表分两堆这个过程中有多少种可能。
g 函数代表分三堆这个过程中有多少种可能。
公式在代码里，意思是，最后新放进去的这个盘子肯定是最小的，可以放在三堆任意一堆堆顶构成新组合，所以是放他之前的所有可能数乘以 3 ，再加上它自成一堆，其他盘子分成两堆的可能数量。
AC代码：
#include <iostream>using namespace std;
typedef long long ll;ll ans[40];ll f(ll x)
{if(x<2)return 0;if(x==2)return 1;return 2*f(x-1)+1;
}ll g(ll x)
{if(x<3)return 0;if(x==3)return 1;return 3*g(x-1)+f(x-1);
}int main()
{int T,N,i;for(i=1;i<30;i++){ans[i]=3+6*f(i)+6*g(i);//cout<<ans[i]<<endl;}while(cin>>T){while(T--){cin>>N;cout<<ans[N]<<endl;}}return 0;
}
AC截图：
这篇关于【递推】【DP】-HDU-1996-汉诺塔⑥的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
