奥法之劫题解 | AlanSP's Blog

这里是 $O(n)$ 的做法。

我们先从一个朴素的 $O(n^3)$ dp讲起。

设 $f[i]$ 表示我处理到 $i$ 号节点的最小代价和，那么转移有：

f[i]=\min(f[k]+\mathrm{cost}(k+1,i))

那么我们可以进行一步步优化到 $O(n)$ 。

先关注 $p_i\geqslant 0$ 的情况，有一些我们不得不拆的 $a_i$ ，我把它们称作“代价”。

这些代价不仅和当前 $i$ 的位置是有关，还与 $b$ 的高度有关。

我们发现代价是不好计算的。随着 $i$ 的变化，代价也随之变化，所以每次都要 $O(n)$ 扫描。

换一种思路，我们可以考虑每个 $a_i$ 对答案的贡献，把它们挂在对应的节点上，就可以快速计算。

也就是说，我们要找到对于每一个 $a_k$ ，找到第一个 $a_i$ ，使得选中 $a_i$ 时必须要拆除 $a_k$ 。

具体而言，我们可以在 $b$ 数组中 $lower\_bound\ a_k$ ，把 $p_k$ 加到对应的高度上。

那么每次我想选一个 $a_i$ ，就必须要拆除所有挂在 $b_j$ 上的代价，因为它们没有被选中且未被挡住。（其中 $a_i=b_j$ ）

这样我们砍掉了计算区间贡献的 $n$ ，而换成了 $\log n$ 。

再想想，由于 $b$ 数组是单调的，所以我们可以一遍扫一遍存下来 $lower\_bound$ 的结果，就可以做到 $O(1)$ 了。

但此时，我们的转移点还是不确定，并且没有考虑 $p_i<0$ 的情况。

对于 $p_i<0$ 的部分，我们贪心的想肯定是越选多越好，所以除了把 $i$ 选中的情况我们的答案都应该加上这些 $p_i$ 。

没错，这里的影响就只和 $i$ 的位置有关了，同样有关的还有我们的 $f$ 数组。

其实我们 $dp$ 的本质，就是在最小化这些东西，而之前的操作是为了方便计算必须要拆的代价。

我们设 $a_i$ 对应的 $b$ 的位置为 $pos_i$ ， $i$ 之前 $p_i<0$ 部分的和为 $sum_i$ ，那么转移有：

f[i]=\min_{pos_k<pos_i}(f[k]-sum_k)+sum_i+cost_{j}

其中 $cost_j$ 表示在 $i$ 位置保留 $b_j$ 高度的代价。

我们发现 $min$ 里面的可以记一个前缀最小值，这样就可以 $O(1)$ 转移了。

这样最小化了能够最小化的部分，也统计了代价。

最后注意几点：

为了保证最后答案能够统计到，要在 $n+1$ 的位置插一个极大值。
如果存在 $a_i\neq b_j$ 对于任意的 $j$ ，那么它不能参与统计答案，但必须要参与代价以及 $sum$ 的计算。
~~其实 $f$ 和 $sum$ 数组根本没必要开。~~~

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int N=5e6+9;
const ll INF=1e18;
inline int read(){
	int res=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		res=(res<<1)+(res<<3)+ch-'0';
		ch=getchar();
	}
	return res*f;
}
int n,a[N],b[N],Q[N],m,pos[N];
ll f[N],g[N],cost[N],p[N],sum;
int main()
{
	// freopen("hs.in","r",stdin);
	// freopen("offa.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) p[i]=read();
	n++,a[n]=n;
	m=read();
	for(int i=1;i<=m;i++) b[i]=read();
    for(int i=1;i<=m;i++) pos[b[i]]=i;
    m++,b[m]=n,pos[n]=m;
	for(int i=1;i<N;i++) g[i]=INF;
    for (int i=1,j=1;i<=n;++i)
	{
		if(b[j]<i) j++;
		Q[i]=j;
	}
	ll tmp=0;
    for (int i=1;i<=n;i++)
    {
		int j=pos[a[i]];
		if(j)
		{
			if(g[j-1]>=INF) f[i]=INF;
			else f[i]=g[j-1]+cost[j]+sum;
		}
		if(p[i]>=0) cost[Q[a[i]]]+=p[i];
		else sum+=p[i];
		if(j&&f[i]<INF) g[j]=min(g[j],f[i]-sum);
	}
    if (f[n]<INF) printf("%lld",f[n]);
    else puts("Impossible");
    return 0;
}