CE求调
  • 板块灌水区
  • 楼主wzc_IOI_czl
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/18 09:39
  • 上次更新2023/11/2 13:07:39
查看原帖
CE求调
539724
wzc_IOI_czl楼主2023/10/18 09:39
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#define maxn 505

using namespace std;

int n, m, a[maxn], b[maxn], f[maxn][maxn][maxn * 2], prel[maxn][maxn][maxn * 2], prer[maxn][maxn][maxn * 2], prv[maxn][maxn][maxn * 2];
map<int, int> mp;
vector<int> g;

void fl(int i, int j, int k, int I, int J, int K, int ex_num = 0) {
	if(f[I][J][K] + ex_num < f[i][j][k]) {
		f[i][j][k] = f[I][J][K] + ex_num;
        prel[i][j][k] = I, prer[i][j][k] = J, prv[i][j][k] = K;
	}
}

void work() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], g.push_back(a[i]);
	cin >> m;
	for(int i = 1; i <= n; i++) cin >> b[i], g.push_back(b[i]);
	g.push_back(-1);
	sort(g.begin(), g.end());
	
	g.erase((vector<int>::iterator)unique(g.begin(), g.end()), g.end());
	for(int i = 1; i < g.size(); i++) mp[g[i]] = i;
	for(int i = 1; i <= n; i++) a[i] = mp[a[i]];
	for(int i = 1; i <= m; i++) b[i] = mp[b[i]];
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			for(int k = 1; k <= n + m; k++) {
				fl(i, j, k, i, j, k - 1);
				fl(i, j, k, i - 1, j, k - 1);
				fl(i, j, k, i, j - 1, k - 1);
				fl(i, j, k, i - 1, j - 1, k - 1, a[i] == a[j]);
			}
		}
	}
	int ans = -1, i0, j0, k0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			for(int k = 1; k <= n + m; k++) {
				if(f[i][j][k] > ans) ans = f[i][j][k], i0 = i, j0 = j, k0 = k;
			}
		}
	}
	while(f[i0][j0][k0] != 0) {
		int i1 = prel[i0][j0][k0], j1 = prer[i0][j0][k0], k1 = prv[i0][j0][k0];
		if(f[i1][j1][k1] < f[i0][j0][k0]) cout << k0 << ' ';
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int _ = 1; /*cin >> _;*/
	 while(_--) work();
}
2023/10/18 09:39
加载中...