Skip to content

Latest commit

 

History

History

3018.Maximum-Number-of-Removal-Queries-That-Can-Be-Processed-I

3018.Maximum-Number-of-Removal-Queries-That-Can-Be-Processed-I

我们令dp[i][j]表示将nums砍至区间[i:j]时,能够通过多少个queries。显然,dp[i][j]是可以由dp[i-1][j]或dp[i][j+1]转化来的。例如,令dp[i-1][j]=t,说明操作至[i-1:j]时已经通过了t个queries,那么如果nums[i-1]>=queries[t]的话,就可以再砍去nums[i-1]使得通过t+1个queries. 反之如果nums[i-1]<queries[t]的话,那么nums[i-1]只能通过预先删除的方法,才能将nums范围收窄至[i:j],即dp[i][j] = dp[i-1][j].

同理,我们也可以写出dp[i][j]由dp[i][j+1]转化来的方程。

这是所有第二类区间型DP中,少数需要先求大区间、再求小区间的题。

本题的初始状态就是dp[0][n-1] = 0,即未做任何操作前,通过的queries的个数是0.

最终我们求所有dp[i][j]中的最大值。但特别需要注意的是,我们只能求得最小长度为1的区间,即dp[i][i],它表示删除到仅剩一个元素nums[i]时通过的queries个数(假设是t)。而然,此时还可以继续删除:只要nums[i]>=queries[t],那么意味着nums可以全部被删除(即通过t+1个queries)。在更新最终答案时需要额外处理这种情况。