Solução Informática Avançado - Semana 46

Solução de Frederico Bulhões

Para resolver esse problema devemos encontrar a maior subsequência comum entre os dois vetores. Depois de encontrado esse valor, podemos então imprimir $n-val$ e $m-val$ , a quantidade de modificações para tornar um vetor equivalente ao outro. Para calular o LCS (longest common substring) podemos fazer a seguinte recorrência, nos vetores a, b:

$LCS(i, j) =$

se $a[i] = b[j]$ :
- $1+LCS(i+1, j+1)$
se $a[i] != b[j]$ :
- $max(LCS(i, j+1), LCS(i+1, j))$

E também levamos em conta os casos base, quando $i > n$ ou $j� > m$ , em que a resposta será zero.

Podemos então usar programação dinâmica, e gravar os resultados para $LCS(i,j))$ em uma tabela e evitar computarmos duas vezes o mesmo resultado.

Código para melhor entendimento:

	//codigo de Lucio Cardoso

	#include <bits/stdc++.h>

	using namespace std;

	const int MAXN = 1010;

	int dp[MAXN][MAXN], s1[MAXN], s2[MAXN];

	// maior subsequência comum
	int lcs(int a, int b)
	{
	if (dp[a][b] != -1) return dp[a][b];
	if (a == 0 \|\| b == 0) return dp[a][b] = 0;

	if (s1[a] == s2[b]) return dp[a][b] = 1+lcs(a-1, b-1);
	else return dp[a][b] = max(lcs(a-1, b), lcs(a, b-1));
	}

	int main(void)
	{
	int n, m;

	cin >> n >> m;

	memset(dp, -1, sizeof dp);

	for (int i = 1; i <= n; i++) cin >> s1[i];
	for (int i = 1; i <= m; i++) cin >> s2[i];

	cout << n-lcs(n, m) << " " << m-lcs(n, m) << "\n";
	}

view raw

maior.cpp

hosted with ❤ by GitHub