- 普及班8月Day15模拟赛
LCIS参考代码
- @ 2025-8-17 15:46:06
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dp[510][510]; // dp[i][j] a1~ai,b1~bj且以bj结尾的LCIS长度
int pre[510][510]; // pre[i][j] 记录在匹配 a[i]==b[j] 时,b 的前驱位置
int a[510], b[510];
vector<int> path;
int LCIS() {
if (n == 0 || m == 0) return 0;
int ans = 0;
int x = 0, y = 0; // 记录最大 dp 值的位置
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i] == b[j])
{
int mx = 0, mx_prek = 0;
for (int k = 1; k < j; k++)
{
if (b[k] < b[j] && dp[i - 1][k] > mx)
{
mx = dp[i - 1][k];
mx_prek = k;
}
}
dp[i][j] = mx + 1;
pre[i][j] = mx_prek;
}
else
dp[i][j] = dp[i - 1][j];
if (dp[i][j] > ans)
{
ans = dp[i][j];
x = i, y = j; // 记录最大值的位置,方便一会从x,y往前回溯路径
}
}
}
// 回溯路径
while (x > 0 && y > 0)
{
if (a[x] == b[y] && dp[x][y] > 0)
{
path.push_back(a[x]);
y = pre[x][y]; // 跳到前一个匹配的位置
x--; // 继续往前找
}
else x--; // 不匹配就往前走
}
reverse(path.begin(), path.end());
return ans;
}
int main()
{
freopen("LCIS.in", "r", stdin);
freopen("LCIS.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++) cin >> b[i];
int len = LCIS();
cout << len << endl;
for (int i = 0; i < path.size(); i++)
cout << path[i] << " ";
return 0;
}
0 条评论
目前还没有评论...