这道题比 CF10D 更难

CF10D 是可以O(n3)O(n^3) dp过的，但是这个只能O(n2)O(n^2)

n^3的思路是，设置f[i][j]f[i][j]表示 A[i]A[i] 与 B[j]B[j] 的最长LCIS，当A[i]==B[j]A[i]==B[j]时，判断F[i−1][k(k−>(0,j−1))]F[i-1][k(k ->(0,j-1))]的最大值。

因此我们得到以下方程。

1
2
3
4
5
6
7
8
9
10
for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		if(a[i]==b[j])
		{
			for(k=0;k<j;k++) 
			if(a[i]>b[k]&&f[i][j]<f[i-1][k]+1)  f[i][j]=f[i-1][k]+1;
		} 
		else f[i][j]=f[i-1][j];
	}

但是这个复杂度太大了，甚至连T=1,N=1000T=1,N=1000都过不了，因此我们要想到优化。

我们发现i,j肯定不能省去，因此我们观察k，发现

若果上一个循环刷新了最大值，一旦a[i]>b[j]a[i]>b[j]那么f[i][j]f[i][j]岂不是可以集成之前的f[i−1][j]f[i-1][j]最大值？

那么我们加一个最大值mxmx，来统计。

需要注意的是，mx做完j的循环都要清空，因为可能a[i]<a[i−1]a[i]<a[i-1] 然后mx继承了比他大的数字的LCIS,然后用在了比他小的LCIS上。

比如

2 5 4
2 5 4
就可能出现
f[2][2]=2;

以下就是dp部分。

1
2
3
4
5
6
7
8
9
10
11
for(i=1;i<=n;i++)
{
	int mx=0;
	for(j=1;j<=m;j++)
    {
		f[i][j]=f[i-1][j];
		if(a[i]==b[j]) f[i][j]=max(f[i][j],mx+1);
		else if(a[i]>b[j]) mx=max(mx,f[i-1][j]);  
		ans=max(ans,f[i][j]);
	}
}

完整版代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<请勿在代码前添加超长预编译指令>

using namespace std;

int f[1100][1100];
int n,m;
int a[1100],b[1100];
int t,ans;

int main()
{
	ios::sync_with_stdio(false);
	int i,j;
	cin>>t; 
	for(t;t>=1;t--)
	{
		memset(f,0,sizeof(f));
		ans=0;
		cin>>n;
		for(i=1;i<=n;i++) cin>>a[i];
		cin>>m;
		for(i=1;i<=m;i++) cin>>b[i];
		for(i=1;i<=n;i++)
		{
			int mx=0;
			for(j=1;j<=m;j++)
			{
				f[i][j]=f[i-1][j];
				if(a[i]==b[j]) f[i][j]=max(f[i][j],mx+1);
				else if(a[i]>b[j]) mx=max(mx,f[i-1][j]);  
				ans=max(ans,f[i][j]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}