A25240. 编程实现：有 n 块长度不同的积木从左到右排成一排，现需要将所有积木按照以下要求堆放在 A、B 位置，A、B 位置初始没有积木。堆放要求：1）从左到右依次拿取积木堆放在 A 位置或 B 位置的顶部，且堆放后不能再改变该积木位置；2）堆放过程中，如果该位置没有积木，那么可以直接堆放拿取的积木；如果该位置有积木，只有拿取的积木长度小于该位置顶部的积木时，才可以堆放。提示：所有积木堆放完后 A 位置或…
填空题
容易
知识点
题目描述
编程实现：
有 n 块长度不同的积木从左到右排成一排，现需要将所有积木按照以下要求堆放在 A、B 位置，A、B 位置初始没有积木。
堆放要求：
1）从左到右依次拿取积木堆放在 A 位置或 B 位置的顶部，且堆放后不能再改变该积木位置；
2）堆放过程中，如果该位置没有积木，那么可以直接堆放拿取的积木；如果该位置有积木，只有拿取的积木长度小于该位置顶部的积木时，才可以堆放。
提示：所有积木堆放完后 A 位置或 B 位置可以没有积木。
例如：n = 2；从左到右 2 块积木的长度依次为 2、1，如下图所示：
按要求，从左到右先堆放长度为 2 的积木，再堆放长度为 1 的积木，有如下 4 种不同的堆放方法：
第一种：先将长度为 2 的积木堆放在 A 位置，因为 1 小于 2，再将长度为 1 的积木堆放在 A 位置顶部；
第二种：先将长度为 2 的积木堆放在 A 位置，再将长度为 1 的积木堆放在 B 位置；
第三种：先将长度为 2 的积木堆放在 B 位置，再将长度为 1 的积木堆放在 A 位置；
第四种：先将长度为 2 的积木堆放在 B 位置，因为 1 小于 2，再将长度为 1 的积木堆放在 B 位置顶部。
给定一个整数 n，以及从左到右 n 块积木的长度，请计算堆放完所有积木，一共有多少种不同的堆放方法；
如果按要求没有一种方法能堆放完所有积木，则输出 0。
输入描述：
第一行输入一个整数 n（1≤n≤20），表示积木数量；
第二行输入 n 个不同的整数（1≤整数≤30），分别表示从左到右每块积木的长度，整数之间以一个空格隔开。
输出描述：
输出一个整数，表示一共有多少种不同的堆放方法；如果按要求没有一种方法能堆放完所有积木，则输出 0。
样例输入：
2
2 1样例输出：
4参考答案
n = int(input（ ）)
blocks = list(map(int, input（ ）.split（ ）))
dp = [[[0] * 31 for _ in range(31)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
x = blocks[i]
for a in range(31):
for b in range(31):
if dp[i][a][b] == 0:
continue
if a == 0 or x < a:
dp[i + 1][x][b] += dp[i][a][b]
if b == 0 or x < b:
dp[i + 1][a][x] += dp[i][a][b]
ans = 0
for a in range(31):
for b in range(31):
ans += dp[n][a][b]
print(ans)
上一题
下一题