文章

11

粉丝

216

获赞

4

访问

103.2k

头像
记录。凡是输入一个 n,要求输出个数和数量的题目,本质都是找规律的题
P1827 复旦大学2019年机试
发布于2021年2月26日 10:26
阅读数 8.1k

#include<iostream>
#include<cstring>

using namespace std;

long long num[25]; //用于记忆化搜索,不然会超时
long long cntBitree(int n)
{
    if (num[n] > 0) return num[n];  //已经计算,直接返回结果

    long long cnt = 0;
    for (int i = 1; i < n; i++)
    {
        cnt += cntBitree(i) * cntBitree(n - i - 1); //模拟左右子树的结点变化,减1是因为根结点占了一个结点数
    }

    //加上线性的两种情况
    cnt += cntBitree(n - 1) * 2;
    num[n] = cnt;

    return cnt;
}

int main()
{
    int n;

    memset(num, 0, sizeof(num));
    num[1] = 1; //边界情况
    num[0] = 0;
    while (cin >> n)
    {
        cout << cntBitree(n) << endl;
    }

    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发