yanbinmu @ 2022-07-16 08:50:01
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
long long f[10005][10005];
int x[10005],y[10005];
int n;
int main()
{
cin>>n;
for(int i = 1 ;i <= n;i++){
cin>>x[i];
}
for(int i = 1 ;i <= n;i++){
cin>>y[i];
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
if(x[i] == y[j]){
f[i][j] = max(max(f[i-1][j],f[i][j-1]),f[i-1][j-1]+1);
}
else{
f[i][j] = max(f[i-1][j],f[i][j-1]);
}
}
}
cout<<f[n][n];
return 0;
}
by Azure__ @ 2022-07-16 08:57:07
dp是过不了的,请自行学习O(n log n)的二分算法
by yanbinmu @ 2022-07-16 09:03:04
@Azure__ 谢谢
by MSqwq @ 2022-07-16 09:23:56