폴리곤 게임은 다각형의 꼭지점과 선분을 이용하여 하는 1인용 게임이다. 게임은 한 다각형의 N개의 꼭지점에서 시작한다.

아래 그림은 N=4일 때의 예이다. 각각의 꼭지점은 임의의 정수를 갖고 있으며,

선분은 각각 +(덧셈)과 *(곱셈)이라는 정보를 가지고 있다.

모서리는 1부터 N까지 번호가 새겨져 있다.

게임을 시작하려면 가장 먼저 꼭지점을 연결하는 선분 중 아무 거나 하나를 없애야 한다.

그 다음부터 게임은 아래와 같이 진행된다.

한 선분 E와 그것이 연결하고 있는 두 꼭지점 V_1과 V_2를 선택한다. 다음, 이것들을 하나의 꼭지점으로 대체한다.

거기에 들어가는 숫자는 V_1과 V_2 꼭지점이 가진 수를 선분에 들어있던 연산자로 연산을 수행한 결과이다.

게임은 선분이 하나도 남지 않으면 끝난다. 그리고 점수는 마지막 남은 꼭지점에든 수이다.

그럼 예제로 이 게임을 하나 해 보자.

위의 다각형을 예로 들어보겠다. 3번 선분을 지우는 것으로 게임을 시작하자. 그러면 다각형은 아래 그림처럼 된다.

그리고 선분 1을 지운다.

다음은 선분 4,

마지막으로 선분 2를 선택하여 게임이 끝났다. 점수는 0점이다.

폴리곤의 정보를 입력받아 이걸로 게임을 했을 때 낼 수 있는 가장 높은 점수를 계산하라.

폴리곤(Polygon) timer 1s memory 64MB

폴리곤(Polygon) 1s 64MB