自动搬运

查看原文

来自洛谷，原作者为

	light_searcher 过去不常常追忆我

搬运于2025-08-24 23:02:52，当前版本为作者最后更新于2024-10-02 07:52:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，肯定是 dp。

设 $f_{i,j}$ 表示 $a$ 序列的前 $i$ 个数和 $b$ 序列中前 $j$ 个数且以 $b_j$ 为结尾的最长上升公共子序列，这里要注意 $a_i$ 不一定是结尾。

为什么设一个这么奇怪的状态呢？我们可以想想其他状态。如果是以 $a_i$ 为结尾且 $b_j$ 为结尾，那么这个状态应该是错误的，因为我们无法保证 $a_i = b_j$。那么如果是 $a$ 的前 $i$ 个数和 $b$ 的前 $j$ 个数呢？你可以自己想想如何转移，反正我觉得这是极其复杂的。那么由此看来上文的状态应该是一个好的选择。

接下来进入正题，考虑如何转移。

分类讨论：

• $a_i \ne b_j$：因为以 $b_j$ 为结尾，所以把 $a_i$ 去掉不会有任何影响，所以 $f_{i,j}=f_{i-1,j}$。
• $a_i = b_j$：只需要在前面找到一个可以把 $b_j$ 接上去的最长公共上升子序列即可。$f_{i,j}= \max\{f_{i-1,k}\}+1$，其中 $1 \le k <j$ 且 $b_k <b_j$。

最后答案是 $\max \{ f_{i,j} \}$。

那么已经有了一个 $\mathcal O(n^3)$ 的做法。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+5;
int n,a[N],b[N],f[N][N],ans;
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(a[i]!=b[j]) f[i][j]=f[i-1][j];
			else{
				int mx=0;
				for(int k=1;k<j;k++)
					if(b[k]<b[j]) mx=max(mx,f[i-1][k]);
				f[i][j]=mx+1;
			}
			ans=max(ans,f[i][j]);
		}
	printf("%lld",ans);
	return 0;
}

结果这么写常数很小，直接跑过了。

但是还是考虑继续优化。发现当 $a_i =b_j$ 时由于 $j$ 枚举时 $i$ 不会变，所以如果 $b_k < a_i$，那么 $f_{i-1,k}$ 就可以纳入到决策集合中，我们最终要用的是决策集合中的最大值，而这个值显然是只增不降的，那我们在枚举 $j$ 的同时就可以完成对这个值的维护。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int n,a[N],b[N],f[N][N],ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++){
		int val=0;
		for(int j=1;j<=n;j++){
			if(a[i]!=b[j]) f[i][j]=f[i-1][j];
			else f[i][j]=val+1;
			if(b[j]<a[i]) val=max(val,f[i-1][j]);
			ans=max(ans,f[i][j]);
		}
	}
	printf("%d",ans);
	return 0;
}