萌新求优化60ptsTLE
查看原帖
萌新求优化60ptsTLE
1270926
wawatime1楼主2025/2/1 09:38
#include <bits/stdc++.h>
using namespace std;
int n, a[100005], b[100005], dp[2][100005];
signed main () {
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf ("%d", &a[i]);
	for (int i = 1; i <= n; i++)
		scanf ("%d", &b[i]);
	int old = 1, now = 0;
	for (int i = 1; i <= n; i++) {
		swap (old, now);
		for (int j = 1; j <= n; j++) {
			if (a[i] == b[j])
				dp[now][j] = dp[old][j - 1] + 1;
			else
				dp[now][j] = max (dp[old][j], dp[now][j - 1]);
		}
	}
	printf ("%d", dp[now][n]);
	return 0;
}
2025/2/1 09:38
加载中...