如果你WAonSubtask#1

B3637 最长上升子序列

hahaha1215 @ 2024-11-10 10:53:18

可以试试这个例子:

5
1 2 3 2 3

原因在于,给定的数组中可能有重复的元素。

当定义f[i]为长度为i的递增子序列的最小结尾元素时

考虑在上面的例子中枚举到a[4],此时f[1]=1,f[2]=2,f[3]=3,如果每次找到第一个大于当前a[1]的f值去更新,那么就会更新f[3]=2,而这样是错误的,原因是f[2]=2,不将a[4]=2连在f[2]=2后面,这样降不满足严格递增。

我们改成去更新第一个大于等于当前a[i]的f值即可AC。


by hahaha1215 @ 2024-11-10 10:56:56

本质上,我们是想找到最后一个小于a[i]的f[j],并且更新f[j+1]

所以改成先找到最后一个小于a[i]的f[j],再更新f[j+1]也是正确的


by Sakura_Love @ 2024-12-05 16:57:43

好!


|