这道题比 CF10D 更难

CF10D 是可以$O(n^3)$ dp过的,但是这个只能$O(n^2)$

n^3的思路是,设置$f[i][j]$表示 $A[i]$ 与 $B[j]$ 的最长LCIS,当$A[i]==B[j]$时,判断$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=1000$都过不了,因此我们要想到优化。

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

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

那么我们加一个最大值$mx$,来统计。

需要注意的是,mx做完j的循环都要清空,因为可能$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;
}