Jogo da Memória

Pedro e Paulo resolveram complicar um pouco o tradicional Jogo da Memória, em que os jogadores precisam virar duas cartas iguais. Eles colocam N cartas no chão, com as faces viradas para baixo. A face de cada carta tem a figura de um número de 1 até N/2, sendo que exatamente duas cartas possuem a figura de cada número entre 1 e N/2. Como as cartas têm as faces viradas para baixo, elas podem também ser identificadas por suas posições, que são inteiros de 1 a N. Pedro e Paulo então desenham no chão, usando giz, algumas linhas ligando pares de cartas, de modo que para qualquer par de cartas (A, B) existe uma e apenas uma sequência de cartas e linhas desenhadas que leva de A até B. A figura abaixo mostra um exemplo de jogo, (a) com todas as cartas com as faces viradas para baixo, e (b) com todas as cartas com as faces viradas para cima.

O jogo é jogado com todas as cartas com as faces viradas para baixo. A cada jogada, o jogador deve escolher um par de cartas A e B. Se as faces das duas cartas escolhidas têm a mesma figura, o jogador acumula um número de pontos igual ao número de linhas desenhadas que existem no caminho entre as cartas A e B. Pedro e Paulo, agora, estão estudando qual é a melhor estratégia para esse jogo e precisam da sua ajuda para resolver uma tarefa específica: dadas as cartas existentes em cada posição, e as ligações desenhadas com giz, calcular o maior valor total de pontos que é possível acumular.