小明是蓝桥王国的勇士，他晋升为蓝桥骑士，于是他决定不断突破自我。 这天蓝桥首席骑士长给他安排了 NN 个对手，他们的战力值分别为 a_1,a_2,...,a_n，且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。 作为热血豪放的勇士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。 请你算算小明最多会挑战多少名对手。 输入格式: 输入第一行包含一个整数 N，表示对手的个数。 第二行包含 N 个整数 a_1,a_2,...,a_n ，分别表示对手的战力值。 1≤N≤10^3 ，1≤a_i≤10^9。 输出格式: 输出一行整数表示答案。

这是一个经典的最长上升子序列问题（LIS）。可以使用动态规划来解决。

定义状态：dp[i] 表示以第 i 个对手为结尾的最长上升子序列的长度。

状态转移方程：dp[i] = max{dp[j]+1}，其中 j<i，且 a[j]<a[i]。

初始状态：dp[1]=1。

最终答案：max{dp[i]}，其中 1≤i≤N。

时间复杂度为 O(N^2)，可以通过此题，但是还有更优秀的 O(NlogN) 算法。

相关问题

蓝桥杯的题目：蓝桥勇士

题目描述：

蓝桥勇士正在探险，来到了一个迷宫。迷宫是一个 n × m 的矩阵，有些格子上有障碍物，有些格子上可以通行。勇士从迷宫的左上角进入，希望尽快到达右下角出口。

勇士有一个特殊的能力，可以在一些格子处花费一定时间，瞬间到达迷宫中任意一处。每个格子至多使用一次这个能力。

勇士希望用最短的时间到达出口，请你帮助他。

输入格式：

第一行包含两个整数 n,m，表示迷宫的行数和列数。

接下来 n 行，每行包含 m 个整数 0 或 1，其中 0 表示对应格子可以通行，1 表示对应格子上有障碍物。

输出格式：

输出勇士到达出口的最短时间，如果无法到达，则输出 −1。

数据范围：

1≤n,m≤1000

输入样例1：

5 5
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0

输出样例1：

8

输入样例2：

5 5
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 1
0 0 0 0 0

输出样例2：

-1

提示：

勇士可以从起点到达的位置，都可以使用能力。

python 蓝桥 印章

根据提供的引用内容，这是一个关于蓝桥Python算法中印章问题的代码。该问题描述了小A买了m张印章，每种图案的出现概率相同，求小A集齐n种印章的概率。

这是一个递归函数`comput(m, n, num)`来计算概率。函数中的参数m表示小A买的印章数量，n表示小A要集齐的印章种类数量，num表示总共的印章种类数量。函数的返回值是小A集齐n种印章的概率。

具体的计算过程如下：
- 如果小A买的印章数量m小于集齐的印章种类数量n，则返回概率为0。
- 如果要集齐的印章种类数量n为1，则返回概率为(1/num)的(m-1)次方。
-则，递归计算小A买m-1张印章集n种印章的概率乘以(n/num)，再加上递归计算小A买m-1张印章集齐n-1种印章的概率乘以((num-n+1)/num)。

最后，根据输入的m和n，调用`comput(m, n, n)`函数计算小A集齐n种印章的概率，并将结果格式化输出。

范例中的代码如下：

def comput(m, n, num):
    if m < n:
        return 0
    elif n == 1:
        return pow(1/num, m-1)
    else:
        return comput(m - 1, n, num) * (n/num) + comput(m - 1, n - 1, num) * ((num - n + 1) / num)

getin = list(map(int, input().split()))
n = getin[0]
m = getin[1]
print("{:.4f}".format(comput(m, n, n)))