多重幂计数问题

多重幂计数问题

时间: 1ms        内存:64M

描述:


设给定n个变量x1 , x2 ,…, xn 。将这些变量依序作底和各层幂,可得n重幂如下:

 

这里将上述n重幂看作是不确定的,当在其中加入适当的括号后,才能成为一个确定的n重幂。不同的加括号方式导致不同的n重幂。例如,当n=4时,全部4重幂有5个。对n个变量计算出有多少个不同的n重幂。

输入:

输入数据只有一行,提供一个数n(n≤50)。

输出:

输出数据只有一行,表示找到的序关系数。

示例输入:

4

示例输出:

5

提示:

参考答案(内存最优[1484]):

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll f[51];
ll dfs(int n)
{
    if(f[n])return f[n];
    ll t=0;
    for(int i=1;i<n;++i)
    {
        t+=dfs(n-i)*dfs(i);
    }
    return f[n]=t;
}
int main()
{
    f[0]=f[1]=f[2]=1;
    int n;
    while(cin>>n)
    cout<<dfs(n)<<endl;
    return 0;
}

参考答案(时间最优[0]):

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll f[51];
ll dfs(int n)
{
    if(f[n])return f[n];
    ll t=0;
    for(int i=1;i<n;++i)
    {
        t+=dfs(n-i)*dfs(i);
    }
    return f[n]=t;
}
int main()
{
    f[0]=f[1]=f[2]=1;
    int n;
    while(cin>>n)
    cout<<dfs(n)<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注