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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |