Solução Festival de Estátuas de Gelo

Solução por Matheus, comentário de João Guilherme

Temos uma questão de dp simples. A dp representa o menor número de blocos necessários para alcansar o tamanho olhado, o único estado é o tamanho que estamos olhando, e a passagem é checar para cada tamanho de bloco se é possível alcansar o estado com o tamanho que estamos analisando menos o bloco olhado, e se for tomar o mínimo.

Segue código para melhor entendimento.


#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 999999999
using namespace std;
int dp [1000500];
int main()
{
int T;
scanf("%d", &T);
for(int z = 0; z< T; z++) {
int coin[100], val, n, i, j;
memset(dp, 0, sizeof(dp));
scanf("%d%d", &n, &val);
for(int i =1;i<=n;i++)
scanf("%d", &coin[i]);
dp[0] = 0;
for(i=1;i<=val;i++) dp[i] = INF;
for(i=1;i<=val;i++)
{
for(j=1;j<=n;j++)
{
if(i - coin[j]>=0)
{
dp[i] = min(dp[i], dp[i-coin[j]] + 1);
}
}
}
printf("%d\n", dp[val]);
}
return 0;
}

view raw

estatuas.cpp

hosted with ❤ by GitHub