Solução André e os Mentos

Solução por João Guilherme

Temos novamente um problema de PD, onde os estados são o começo do nosso segmento de mentos e o fim. A passgem é simples, se o mentos do começo for igual ao do fim, removemos ambos, se eles forem distintos tomamos o mínimo entre remover cada um deles.

Segue código para melhor entendimento.


#include <bits/stdc++.h>
using namespace std;
int dp[1010][1010], mentos[1010];
int f(int beg, int fim){
if(beg > fim) return 0;
if(beg == fim) return 1;
if(dp[beg][fim] != 0) return dp[beg][fim];
if(mentos[beg] == mentos[fim]) return dp[beg][fim] = 1 + f(beg + 1, fim - 1);
return dp[beg][fim] = 1 + min(f(beg + 1, fim), f(beg, fim - 1));
}
int main(){
int n, t;
scanf("%d", &t);
for(int q = 1; q <= t; ++q){
memset(dp, 0, sizeof dp);
memset(mentos, 0, sizeof mentos);
scanf("%d", &n);
for(int i = 0; i < n; ++i) scanf("%d", &mentos[i]);
printf("Caso #%d: %d\n",q, f(0, n - 1));
}
return 0;
}

view raw

mentos.cpp

hosted with ❤ by GitHub