阶梯__牛客网

你有n个箱子，它们的高度分别为ai，你想要用它们做出一个尽可能长的阶梯。但是你对最长的阶梯长度不感兴趣，你只对其方案数感兴趣。形式化地，给出长度为n的序列{ai}，从中挑选出子序列{bi}，满足对所有合法下标i,有bi<bi+1成立(即单调递增)(如果子序列{bi}长度为
1，亦视为满足此条件)。在这些子序列中，长度为最大长度的子序列有多少个? (子序列:某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列。例如{2,3,5}是 {1,2,3,4,5}的子序列，而{2,1}和{1,6}不是。
我们认为两个子序列相同，当且仅当所有数都是从相同位置选出来的。而对于序列{1,2,2,6}，选择第2个和第4个形成子序列{2,6}，选择第 3个和第4个形成子序列{2,6}，虽然形式相同但仍视为不同的序列，因为前者的2是原序列中第2个，后者的2是原序列中的第3个，并非相同位置选出)

if __name__ == "__main__": n = int(input()) a = list(map(int, input().split())) dp = [1]*n #表示以第i个箱子为结尾的最长递增子序列的长度 count = [0]*(n+1)# count[i] 表示长度为i的递增子序列的个数 count[1] = 1 max_len = 1 for i in range(1, n): for j in range(i): if a[j]<a[i]: if dp[j]+1>dp[i]: #说明是一条路线 dp[i] = dp[j]+1 count[dp[i]] = count[dp[j]] elif dp[j]+1==dp[i]: count[dp[i]] += count[dp[j]] max_len = max(max_len, dp[i]) print(count[max_len])

n = int(input()) seq = [int(i) for i in input().split()] order_seq_length = [1]*n mod = 1000000007 solutions = 0 max_len = 0 max_len_end = -1 for i in range(n): cur = seq[i] max_len_at_left = 0 for k in range(i-1,-1,-1): if seq[k] < cur: max_len_at_left = max(max_len_at_left, order_seq_length[k]) break order_seq_length[i] = max_len_at_left+1 if max_len < order_seq_length[i]: max_len = order_seq_length[i] max_len_end = i for i in range(max_len_end, n): cur_solutions = 0 if order_seq_length[i] == max_len: cur_solutions = 1 max_end_num = seq[i] cur_len = max_len-1 count = 0 min_max = max_end_num j = max_len_end while j >= 0: if seq[j]<max_end_num and order_seq_length[j] == cur_len: count += 1 min_max = min(min_max, seq[j]) j-=1 elif seq[j]<max_end_num and order_seq_length[j] == cur_len-1: cur_solutions *= max(count,1) % mod count = 0 max_end_num-=min_max cur_len-=1 else: j -= 1 cur_solutions *= max(count,1) % mod solutions += cur_solutions % mod print(solutions)

阶梯

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题