Solução por Rogério Júnior
Para ver o problema original, clique aqui.
O problema é uma função recursiva muito simples. O estado da recursão será a posição do dado da pilha que estamos olhando (onde o topo é 1) e e qual a face dele que está virada para cima (
), e ela retornará o maior valor de um lado da sub-pilha formada por este dados e os abaixo dele. Sabendo a face de cima de um dado, sabemos qual a de baixo pelo desenho. Chamaremos faces A, B, ..., F de faces 1, 2, ..., 6, onde ![dado[pos][i]](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_2d53811718069beccea423ef26999d15.gif?w=640&ssl=1)
guarda qual o número da face 
no dado na posição 
.
Para um estado, percorreremos todas as faces que não são topo ou cima e usaremos a melhor para o lado da pilha que terá valor máximo. Chamaremos este valor de 
. Se o dado olhado for o último, retornamos . Olharemos o próximo dado, procurando qual de duas faces tem o mesmo valor da face de baixo do dado (seja ela 
), e chamaremos a recursão agora com esta sendo a face de cima (
).
No final, chamamos a recursão para cada uma das possíveis faces de cima do primeiro dado. Note que a melhor resposta da recursão para o primeiro dado soluciona o problema. Segue o 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 <iostream> | |
| #include <algorithm> | |
| #include <cstring> | |
| using namespace std; | |
| #define endl '\n' | |
| #define ends ' ' | |
| #define MAXN 10100 | |
| int n, dado[MAXN][10]; | |
| int solve(int pos, int cima){ | |
| int baixo=0, best_face=0; | |
| // sabendo a face de cima, descubro a de baixo | |
| if(cima==1) baixo=6; | |
| if(cima==2) baixo=4; | |
| if(cima==3) baixo=5; | |
| if(cima==4) baixo=2; | |
| if(cima==5) baixo=3; | |
| if(cima==6) baixo=1; | |
| // olho qual a melhor face que estará voltada | |
| // para o lado de soma máxima da pilha | |
| for(int i=1; i<=6; i++) | |
| if(i!=cima and i!=baixo) | |
| best_face=max(best_face,dado[pos][i]); | |
| // se o dado olhado for o último, esta face representa | |
| // o lado de maior soma pois só ele constitui sua sub-pilha | |
| if(pos==n) return best_face; | |
| int new_cima=0; | |
| // descubro qual o lado do próximo lado que está voltado apra cima | |
| for(int i=1; i<=6; i++) | |
| if(dado[pos+1][i]==dado[pos][baixo]) | |
| new_cima=i; | |
| // e chamo a recursão para o próximo dado | |
| return best_face+solve(pos+1,new_cima); | |
| } | |
| int main(){ | |
| ios_base::sync_with_stdio(false), cin.tie(0); | |
| cin >> n; | |
| // leio os lados de cada dado | |
| for(int i=1; i<=n; i++) cin >> dado[i][1] >> dado[i][2] >> dado[i][3] >> dado[i][4] >> dado[i][5] >> dado[i][6]; | |
| // e olho qual o melhor lado do primeiro dado para estar para cima | |
| int maior=0; | |
| for(int i=1; i<=6; i++) maior=max(maior,solve(1,i)); | |
| // imprimo o valor obtido na melhor recursão | |
| cout << maior << endl; | |
| return 0; | |
| } |