[AHOI2012]树屋阶梯

NC19891. [AHOI2012]树屋阶梯

描述

暑假期间，小龙报名了一个模拟野外生存作战训练班来锻炼体魄，训练的第一个晚上，教官就给他们出了个难题。由于地上露营湿气重，必须选择在高处的树屋露营。小龙分配的树屋建立在一颗高度为 N+1 尺（ N 为正整数）的大树上，正当他发愁怎么爬上去的时候，发现旁边堆满了一些空心四方钢材（如图 1.1 ），经过观察和测量，这些钢材截面的宽和高大小不一，但都是 1 尺的整数倍，教官命令队员们每人选取 N 个空心钢材来搭建一个总高度为 N 尺的阶梯来进入树屋，该阶梯每一步台阶的高度为 1 尺，宽度也为 1 尺。如果这些钢材有各种尺寸，且每种尺寸数量充足，那么小龙可以有多少种搭建方法？（注：为了避免夜里踏空，钢材空心的一面绝对不可以向上。）

以树屋高度为4尺、阶梯高度N=3尺为例，小龙一共有如图1.2所示的5种搭建方法：

输入描述

一个正整数 N(1 ≤ N ≤ 500)，表示阶梯的高度

输出描述

一个正整数，表示搭建方法的个数。（注：搭建方法个数可能很大。）

示例1

输入:

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3(pypy3.6.1) 解法, 执行用时: 42ms, 内存消耗: 18696K, 提交时间: 2020-08-17 16:37:48

n = int(input())
ans = 1
for i in range(n+1, 2*n+1):
    ans *= i
for i in range(1, n+2):
    ans //= i
print(int(ans))

Python(2.7.3) 解法, 执行用时: 11ms, 内存消耗: 2844K, 提交时间: 2021-05-02 14:33:05

h=[0]*501
h[0]=h[1]=1
for i in range(2,501):
    h[i]=h[i-1]*(4*i-2)/(i+1)
n=int(raw_input())
print h[n]

Python3 解法, 执行用时: 42ms, 内存消耗: 4540K, 提交时间: 2023-08-11 10:56:51

n = int(input())
c = 1;
for i in range(1,n+1):c = c*(4*i-2)//(i+1)
    
print(c)

上一题

下一题

详情