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,

$\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