Solução Pilha de Dados

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 (solve(pos,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] guarda qual o número da face i no dado na posição pos.

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 bestface. Se o dado olhado for o último, retornamos bestface. Olharemos o próximo dado, procurando qual de duas faces tem o mesmo valor da face de baixo do dado pos (seja ela new_cima), e chamaremos a recursão agora com esta sendo a face de cima (solve(pos+1,new_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:


#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;
}

view raw

dados.cpp

hosted with ❤ by GitHub