T321704 - 洛谷保存站

# Solution#1

对于 $5\%$ 的数据，if else 特判即可。

# Solution#2

考虑分别 $O(2^n)$ 枚举排列，直接爆算即可。

得分 $20$

# Solution#3

设计 $dp$ ，令 $f_{i,j}$ 为 $A$ 排列中做到第 $i$ 个值， $B$ 中做到第 $j$ 个值。

$if \ \ \ \ \ A_i=B_j  \ \ \ \ \ \ \ \ f_{i,j}=f_{i-1,j-1}+A_i$

$otherwise\ \ \ \ \ \ \ \ f_{i,j}=max(f_{i-1,j},f_{i,j-1})$

得分 $40$ 。

# Solution#4

我们注意到这是个排列，也就意味着 $A$ 中的每个元素有且仅有一个对应值。

比如样例：

有如下几对的对应：

$(1,4)$

$(2,5)$

$(3,3)$

$(4,2)$

$(5,1)$

这个就转换成了一个二维偏序。

最佳方案：$(5,1)$

而我们固定住每对的第一个元素，排个序，我们就发现这是一个求 $(4,5,3,2,1)$ LIS 的问题。

树状数组即可解决。

Code：

```cpp
#include<iostream>
using namespace std;
int n,p[100005][2],wz[100005],dy[100005],tree[100005],f[100005],anss;
void add(int x,int k){
	while(x<=n){
		tree[x]=max(tree[x],k);
		x+=x&-x;
	}
}
int qry(int x){
	int ret=0;
	while(x){
		ret=max(tree[x],ret);
		x-=x&-x;
	}
	return ret;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i][0];
	} 
	for(int i=1;i<=n;i++){
		cin>>p[i][1];
		wz[p[i][1]]=i;
	}
	for(int i=1;i<=n;i++){
		dy[i]=wz[p[i][0]];
	}
	for(int i=1;i<=n;i++){
		f[i]=qry(dy[i])+p[i][0];
		anss=max(anss,f[i]);
		add(dy[i],f[i]);
	}
	cout<<anss;
	return 0;
} 
```

正在渲染内容...