O(n) 做法

首先我们一开始设置了 $\tt dp_{i,j}$ 表示考虑到 $\tt a$ 数组的第 $\tt i$ 个，$\tt b$ 数组的第 $\tt j$ 个的答案。

这个就分情况转移：

$a_i \lt b_j$ ，可以保留，转移方程：$\min\{dp[i-1][j], dp[i-1][j]+p[i]\}$
$a_i>b_j$ ，不可保留，转移方程：$dp[i-1][j]+p[i]$
$a_i = b_i$ ，可以保留，转移方程：$\min\{dp[i-1][j-1],dp[i-1][j],dp[i-1]+p[i]\}$

然后发现这个做法显而易见会爆掉，优化。

我们给 $\tt dp$ 数组压一维，变成 $\tt dp_i$ 表示考虑到 $\tt a$ 数组的第 $\tt i$ 个的代价。与原来变化不大。如果 $a_i$ 是 $b$ 数组里面的数字，我们需要转移；如果不是，就直接忽略。转移方程：

$dp_i = \min\limits_{x=1}^{i-1}\left(dp_x+\sum\limits_{k=x+1}^{i-1}[a_k\gt b_{j-1} || p_k\lt0]p_k\right)$

其中上面的和式中的东西可以拆成 $a_k>b_{j-1},p_k≥0$ 与 $p_k<0$ 两部分。后一部分可以用前缀和维护，前一部分可以用树状数组维护。

然后这道题我们发现这样转移需要枚举一个 $x$ ，复杂度还是不够，继续优化。我们考虑如何可以免去这个 $x$ 的枚举。我们用前缀最小值优化，因为这个 $dp_i$ 只会从满足条件的 $dp_x$ 转移。转移方程再变成

$dp_i = \min\limits_{x=1}^{i-1}\left(dp_x+\sum\limits_{k=x+1}^{i-1}[a_k\gt b_{j-1}\ \&\&\ p_k\ge0]p_k+\sum\limits_{k=x+1}^{i-1}[p_k\lt0]p_k\right)$

我们设置前缀和数组 $sum1,sum2$ 分别表示：

$sum1_x=\sum\limits_{k=1}^{x}[a_k\gt b_{j-1}\ \&\&\ p_k\ge0]p_k\\ sum2_x=\sum\limits_{k=1}^{x}[p_k\lt0]p_k$

带入到刚刚的转移方程种，就变成了：

$dp_i = \min\limits_{x=1}^{i-1}\left(dp_x+sum1_{i-1}-sum1_x+sum2_{i-1}-sum2{x}\right)$

然后我们就记录一个数组 $g$ 表示我们要求的前缀最小值

$g_y=\min\limits_{x=1}^{k-1}(dp_x-sum1_x-sum2_x)[a_x=y]$

方程就进化成

$dp_i=g_{b_{j-1}} + sum1_{i-1} + sum2_{i-1}$

最后再递推的同时处理 $g_{a_i}$ 。但是这个 $sum1$ 数组还是要树状数组。

发现复杂度都砸在了求 $sum1_x$，我们考虑重构状态转移方程。考虑贡献后移。我们称区间 $(b_{j-1},b_j]$ 为“区间 $j$ ”。在计算 $dp$ 时，我们可以只考虑满足 $a_k$ 在“区间 $j$ ”中的 $k$ 的贡献，从当前来看，并没把该删的都删了，比如说 $a_k >b_i$ 的就没有删掉；但是从整体上来看，最后该删掉的就是 $a_k$ 在每一个区间中的 $k$ ，而计算完 $dp_n$ 时，我们已经将所有的 ”区间“ 都算完了，所以这样 DP 是不影响最后答案的。

我们预处理出每一个位置 $k$ 它的 $a_k$ 所在的“区间 $g_k$”，实时维护 $h_l$ 表示这时“区间 $l$ ”要删掉的元素的代价总和，并且将 $g_y$ 改为只需要记录 $dp－ sum2$ 的前缀最小值。那么就有新的方程：

$dp_i = g_{b_{j-1}} + sum2_{i-1} + h_j$

因为 $b$ 数组单调递增，所以双指针就好了。