一个哥们写的,样例不能完全通过
时间太慢了
大佬们,看看能不能改进一下
import itertools
B = [3, 3, 9, 9, 9, 7, 7, 8, 8, 8]
n = 10
# B = [8, 6, 2, 2, 8, 8]
# n = 6
# A中每一项的上界为对应3项中的最小值
A_max = [min(B[x - 1], B[x], B[(x + 1) % n]) for x in range(n)]
A = [list(range(i + 1)) for i in A_max]
# A = [a, b, c, d, e]
# B = [x-, x, x, x+, x+]
# e, a, b <= x- 且至少有一个x-
# a, b, c <= x 且至少有一个x
# 可知 c = x
# 总结: 如果 B[i] < B[(i + 1) % n], 则A[(i + 2) % n] = B[(i + 1) % n]
# 对于B[i] > B[(i + 1) % n], 也是同理
for i in range(n):
if B[i] < B[(i + 1) % n]:
A[(i + 2) % n] = [B[(i + 1) % n]]
elif B[i] > B[(i + 1) % n]:
A[i - 1] = [B[i]]
def check(a: list) -> bool:
for i in range(n):
if B[i] != max(a[i - 1], a[i], a[(i + 1) % n]):
return False
return True
A = itertools.product(*A)
counter = 0
for a in A:
if check(a):
counter += 1
print(counter % 1000000007)
|