Q_6_8.cpp

Q_6_8.cpp

#include <bits/stdc++.h>
#include <iostream>
#include <string>

using namespace std;

int TopDown(const string &str_a, const string &str_b, const int idx_a, const int idx_b, vector<vector<int>> &dp, int &max_ans)
{
	if (idx_a == str_a.size()) {
		return 0;
	}
	if (idx_b == str_b.size()) {
		return 0;
	}

	if (dp[idx_a][idx_b] != -0xC8763) {
		return dp[idx_a][idx_b];
	}

	int ans;

	if (str_a[idx_a] == str_b[idx_b]) {
		ans = max(0, TopDown(str_a, str_b, idx_a + 1, idx_b + 1, dp, max_ans)) + 8;
	} else {
		int a = max(0, TopDown(str_a, str_b, idx_a + 1, idx_b, dp, max_ans)) - 3;
		int b = max(0, TopDown(str_a, str_b, idx_a, idx_b + 1, dp, max_ans)) - 3;
		int c = max(0, TopDown(str_a, str_b, idx_a + 1, idx_b + 1, dp, max_ans)) - 5;

		ans = max(a, b);
		ans = max(ans, c);
	}

	dp[idx_a][idx_b] = ans;

	max_ans = max(max_ans, ans);
	return ans;
}

int main()
{
	string str_a;
	string str_b;
	int max_ans = INT_MIN;

	getline(std::cin, str_a);
	getline(std::cin, str_b);

	vector<vector<int>> dp(str_a.size(), vector<int>(str_b.size(), -0xC8763));

	TopDown(str_a, str_b, 0, 0, dp, max_ans);

	cout << max_ans << endl;

	return 0;
}