ttltony @ 2023-01-31 15:07:31
#include <iostream>
#include <algorithm>
using namespace std;
int n, ans;
int a[10001], b[10001], dp[10001][10001];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) cin >> b[i];
for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) {
if (dp[i][j]) continue;
if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) ans = max(ans, dp[i][j]);
cout << ans << endl;
return 0;
}
代码如上,求问
by DreamLand_zcb @ 2023-01-31 15:12:37
@ttltony LIS的二分优化好像和你dp思路不一样
g[0]=-INF;
for(int i=1;i<=n;i++) g[i]=INF;
for(int i=1;i<=n;i++)
{
f[i]=upper_bound(g, g+n+1, a[i])-g;
g[f[i]]=a[i];
ans=max(ans, f[i]);
}
by DreamLand_zcb @ 2023-01-31 15:18:41
@ttltony 开个桶表示p1[i]在p2中第一次出现的下标,然后再用LIS和二分优化
by ttltony @ 2023-01-31 15:47:04
@DreamLand_zcb 谢谢大佬QWQ