题解：P10236 [yLCPC2024] D. 排卡

ran_qwq · 2024-03-14 16:29:27 · 题解

把删数反过来变成加数，初始双端队列为空，每次可以将左边或右边的数加入双端队列。

因为任何时候加的都是一个区间，所以考虑区间 dp，设 dp_{i,j,0/1} 为加 i 到 j 的数，上一个取的是最左边 / 最右边的数，当前分数的最大值。

边界：dp_{i,i,0}=dp_{i,i,1}=0，只加了一个数。

状态转移方程：

• 对于 dp_{i,j,0}，新加的数是 a_i，从 dp_{i+1,j,0/1} 转移过来，上一次可以加 a_{i+1} 或 a_j。所以 dp_{i,j,0}=\max(dp_{i+1,j,0}+a_i^{a_j},dp_{i+1,j,1}+a_i^{a_i+1})。注意我们把原问题反过来了，所以得出的 b 数组也是反过来的，dp 时要把它反回去。

• 对于 dp_{i,j,1}，新加的数是 a_i，从 dp_{i,j-1,0/1} 转移过来，上一次可以加 a_i 或 a_{j-1}。所以 dp_{i,j,1}=\max(dp_{i,j-1,0}+a_i^{a_j},dp_{i,j-1,1}+a_j^{a_j-1})。

答案：\max(dp_{1,n,0},dp_{1,n,1})。