scpc 예선 round2 유사도

#include "pch.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

int a[5005];
int b[5005];
int dp[5005][5005];

//회전하지 않은 결과값 저장
int start[5005];
int Dend[5005];

int main() {
	setbuf(stdout, NULL);
	int T;
	cin >> T;
	for (int test = 1; test <= T; test++) {
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		for (int i = 0; i < n; i++) {
			cin >> b[i];
		}
		memset(dp, 0, sizeof(dp));
		memset(start, 0, sizeof(start));
		memset(Dend, 0, sizeof(Dend));

		start[0] = (a[0] == b[0] ? 1 : 0);
		Dend[n - 1] = (a[n - 1] == b[n - 1] ? 1 : 0);
		for (int i = 1; i < n; i++) {
			start[i] = start[i - 1] + (a[i] == b[i] ? 1 : 0);
			Dend[n - 1 - i] = Dend[n - i] + (a[n - 1 - i] == b[n - 1 - i] ? 1 : 0);
		}

		int maximum = 0;

		for (int i = 0; i < n; i++) {
			//홀수 계산
			dp[i][i] = (a[i] == b[i] ? 1 : 0);
			maximum = max(maximum, start[n - 1]);
			int sum = dp[i][i];
			for (int j = 1; j < n; j++) {
				if (i - j < 0 || i + j >= n) break;
				dp[i - j][i + j] = sum + (a[i - j] == b[i + j] ? 1 : 0) + (a[i + j] == b[i - j] ? 1 : 0);
				sum = dp[i - j][i + j];
				maximum = max(maximum, start[i - j - 1] + sum + Dend[i + j + 1]);
			}

			//짝수 계산
			dp[i][i + 1] = (a[i] == b[i + 1] ? 1 : 0) + (a[i + 1] == b[i] ? 1 : 0);
			sum = dp[i][i + 1];
			maximum = max(maximum, start[i - 1] + dp[i][i + 1] + Dend[i + 2]);
			for (int j = 1; j < n; j++) {
				if (i - j < 0 || i + 1 + j >= n) break;
				dp[i - j][i + 1 + j] = sum + (a[i - j] == b[i + 1 + j] ? 1 : 0) + (a[i + 1 + j] == b[i - j] ? 1 : 0);
				sum = dp[i - j][i + 1 + j];
				maximum = max(maximum, start[i - j - 1] + sum + Dend[i + j + 2]);
			}
		}

		printf("Case #%d\n%d\n", test,maximum);
	}
}