题解：CF2121H Ice Baby

· · 题解

我的做法

考虑对于每个数，它的选取只有两种情况

1.取l_i

2.取和非严格递增子列中上一个数相同的值

设dp[i]为最后一个数为i时子列的最大长度

用线段树维护这个dp数组

每加进来一个数，模拟这两种情况

1：将l_i点的值变为[1,l_i]区间的最大值再+1

2：使所有l_i到r_i的值+1

答案统计：取最大值

官方解法

设dp_i为长度为i的子列最后一项的最小值

为方便说明，不妨设$dp[i]-dp[j]$恰好对应对于所有值在$[l_i,r_i]$的dp值 首先，可以在这一位补一个和子列最后一个数相同的数，那么就相当于$dp[i]-dp[j]$转移为了$dp[i + 1]-dp[j + 1]

需要把原来的dp[j + 1]给删了用来“让位”

同时，这一位可以取l_i放在dp[i - 1]的后面，把dp[i]变为l_i（因为原来的dp[i]比l_i大所以这样一定更优）

至此，这一轮的乾坤大挪移就完成了