母题

求最长上升子序列。

令 \(f_i\) 表示以 \(i\) 结尾的答案，然后考虑对于 \(a_i>a_j,f_i=\max(f_j+1)\)。

1

类似，但是需要预处理，结构是一样的。

2

前缀和、差分，还是很类似。

3

多记录当前选取的子段个数，考虑最后一段选取即可。

4

状态还是前xxx+“<” 个数。

考虑新的数放的位置，由于当前数字是最大的，所以只可能增加一个 \(>,<\)，考虑大于小于的个数，即可确定插入的位置有几个，根据乘法原理即可。

https://www.acwing.com/activity/content/code/content/6991643/

简单的拆解成上升段和下降段。

https://www.cnblogs.com/wscqwq/p/17416716.html

利用贪心思想，然后求解母题。

https://www.cnblogs.com/wscqwq/p/17416717.html

爆搜加贪心，还是动态规划的思想。

https://www.cnblogs.com/wscqwq/p/17589856.html

数字最终变换完后只有两种可能，我们状态就是分别记录两种的个数，然后根据已有的和可以计算出当前的数应该的取值。

https://www.cnblogs.com/wscqwq/p/17609388.html

前xxx+乘号个数。

考虑最后一个乘号即可。

高精度可以实现成只有两位。

https://www.cnblogs.com/wscqwq/p/17621465.html

暴力破环，然后就是上题做法。

https://www.cnblogs.com/wscqwq/p/17644083.html

关键是根据最值来判断最多会用几次跳过。

可以确定一个上界，那么就可以采用最后的点，跳过的点数的状态。

https://www.acwing.com/activity/content/code/content/6994539/

需要用到一个数学公式，然后就可以将中间过长的区间进行放缩，使得原来从哪里能跳到一个位置，现在还是可以，即与原来等价。矩阵优化也许也可行。

https://www.acwing.com/activity/content/code/content/6994965/

前xxx+前xxx+已用个数。

然后利用方程之间的关系，采用类似前缀和式优化。

特征

问题都是一个序列上的，而且只需要考虑当前新加的数字即可。状态可能是前xxx或者是最后一个是xxx，附加其他属性。