Solução Intermediário - Semana 55 - Problema 1

Para esse problema usaremos o algoritmo de troco. Defina $dp[m]$ como o número mínimo de tacadas para se chegar à distância $m$ e $taco[i]$ como a distância do i-ésimo taco. Então,

$dp[m] = \begin{cases} 0 & ,\mbox{se m = 0} \\ \min\limits_{0 \leq i < N}( dp[m - taco[i]] + 1) & , \mbox{caso m > 0} \end{cases}$

Código para melhor entendimento:

Complexidade: $\mathcal{O}(n\cdot d)$

	#include <bits/stdc++.h>
	using namespace std;
	const int maxn = 6000;
	const int inf = (int)1e8 + 10;

	int n, m, dp[maxn], taco[maxn];
	int main()
	{
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> m >> n;

	for(int i = 0; i < n; i++)
	{
	cin >> taco[i];
	}

	dp[0] = 0;

	for(int i = 1; i <= m; i++){
	dp[i] = inf;
	for(int j = taco[i]; j < n ; j++)
	if(i - taco[j] >= 0)
	dp[i] = min(dp[i], dp[i - taco[j]] + 1);
	}

	if(dp[m] == inf)
	cout << "Luiza perde o jogo.";
	else
	cout << "Luiza ganha em " << dp[m] << " tacadas.";

	return 0;
	}

view raw

ints55p1.cpp

hosted with ❤ by GitHub