美团笔试820

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<unordered_map>
using namespace std;

// 交替输出字符串
void first() {
	int n = 0;
	cin >> n;
	string line1, line2;
	cin >> line1;
	cin >> line2;

	for (int i = 0; i < n; i++) {
		cout << line1[i] << line2[i];
	}
}
// 通信坐标最小
void second() {
	int n = 0;
	cin >> n;
	int x1 = 0, x2 = 0, x3 = 0, y1 = 0, y2 = 0, y3 = 0;
	cin >> x1 >> y1;
	cin >> x2 >> y2;
	cin >> x3 >> y3;
	int d1 = 0, d2 = 0, d3 = 0;
	cin >> d1 >> d2 >> d3;
	set<string> s1, s2;

	int ansx = INT32_MAX, ansy = INT32_MAX;
	for (int x = x1 - d1; x < x1 + d1; x++) {
		if (x <= 0 || x > n) continue;

		int xd = abs(x - x1);
		int left = d1 - xd;
		if (left == 0) {
			string k = to_string(x) + " " + to_string(y1);
			s1.insert(k);
		}
		else {
			int yy1 = y1 - left;
			int yy2 = y1 + left;
			if (yy1 > 0 && yy1 <= n) {
				string k = to_string(x) + " " + to_string(yy1);
				s1.insert(k);
			}
			if (yy2 > 0 && yy2 <= n) {
				string k = to_string(x) + " " + to_string(yy2);
				s1.insert(k);
			}
		}
	}
	
	for (int x = x2 - d2; x < x2 + d2; x++) {
		if (x <= 0 || x > n) continue;

		int xd = abs(x - x2);
		int left = d2 - xd;
		if (left == 0) {
			string k = to_string(x) + " " + to_string(y2);
			if (s1.count(k))
				s2.insert(k);
		}
		else {
			int yy1 = y2 - left;
			int yy2 = y2 + left;
			if (yy1 > 0 && yy1 <= n) {
				string k = to_string(x) + " " + to_string(yy1);
				if(s1.count(k))
					s2.insert(k);
			}
			if (yy2 > 0 && yy2 <= n) {
				string k = to_string(x) + " " + to_string(yy2);
				if (s1.count(k))
					s2.insert(k);
			}
		}
	}


	for (int x = x3 - d3; x < x3 + d3; x++) {
		if (x <= 0 || x > n) continue;

		int xd = abs(x - x3);
		int left = d3 - xd;
		if (left == 0) {
			string k = to_string(x) + " " + to_string(y3);
			if (s2.count(k)) {
				if (ansx > x || ansx == x && ansy > y3) {
					ansx = x;
					ansy = y3;
				}
			}
				
		}
		else {
			int yy1 = y3 - left;
			int yy2 = y3 + left;
			if (yy1 > 0 && yy1 <= n) {
				string k = to_string(x) + " " + to_string(yy1);
				if (s2.count(k)) {
					if (ansx > x || ansx == x && ansy > y3) {
						ansx = x;
						ansy = yy1;
					}
				}
			}
			if (yy2 > 0 && yy2 <= n) {
				string k = to_string(x) + " " + to_string(yy2);
				if (s2.count(k)) {
					if (ansx > x || ansx == x && ansy > y3) {
						ansx = x;
						ansy = yy2;
					}
				}
			}
		}
	}


	cout << ansx<<" "<<ansy;

}

// 复习获取最大期望
void third() {
	int n = 0, m = 0;
	cin >> n >> m;
	int i = 0;
	int num = 0;
	vector<int> p(n, 0), scores(n, 0);
	while (i < n) {
		cin >> num;
		p[i++] = num;
	}
	i = 0;
	while (i < n) {
		cin >> num;
		scores[i++] = num;
	}

	vector<pair<int,double>> tmp(n,{0,0});
	for (i = 0; i < n; i++) {
		tmp[i] = { i,(double)(100 - p[i]) / (double)100 * (double)scores[i] };
	}

	sort(tmp.begin(), tmp.end(), [&](const pair<int, double>& a, const pair<int, double>& b) {
		return a.second > b.second;
		});
	set<int> indexs;
	for (i = 0; i < m; i++) {
		indexs.insert(tmp[i].first);
	}
	double sum = 0;
	for (i = 0; i < n; i++) {
		if (indexs.count(i)) {
			sum += scores[i];
		}
		else {
			sum += (double)scores[i] * (double)p[i] / 100.0;
		}
	}

	printf("%.2f", sum);
}

 
long dp(vector<int>& s1, vector<int>& s2, int i, int j, unordered_map<long, long>& memo) {
	if (i < 0 && j < 0)
		return 0;
	int key = i * 20000 + j;
	if (memo.count(key)) {
		return memo[key];
	}
	long i_c = LONG_MAX;
	long j_c = LONG_MAX;
	long cc = LONG_MAX;
	if (i >= 0 && j >= 0) {
		cc = abs(s1[i] - s2[j]) + dp(s1, s2, i - 1, j - 1, memo);
		i_c = abs(s1[i]) + dp(s1, s2, i - 1, j, memo);
		j_c = abs(s2[j]) + dp(s1, s2, i, j - 1, memo);
	}
	else if (i >= 0) {
		i_c = abs(s1[i]) + dp(s1, s2, i - 1, j, memo);
	}
	else if (j >= 0) {
		j_c = abs(s2[j]) + dp(s1, s2, i, j - 1, memo);
	}

	memo[key] = min(min(i_c, j_c), cc);

	return memo[key];

}

// 同步两个字符串的最小距离
void forth() {
	int n = 0, m = 0;
	cin >> n >> m;
	int i = 0;
	int num = 0;
	vector<int> s1(n, 0), s2(m, 0);
	while (i < n) {
		cin >> num;
		s1[i++] = num;
	}
	i = 0;
	while (i < m) {
		cin >> num;
		s2[i++] = num;
	}

	unordered_map<long, long> memo;

	long ans = dp(s1, s2, n - 1, m - 1, memo);
	cout << ans;
}
int main() {
	forth();

	return 0;
}