IOI 1998 day2 3- 폴리곤(Polygon) > 문제은행 : 정보올림피아드&알고리즘




1321 : 폴리곤(Polygon)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
22 회   
시도횟수
65 회   

문제

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

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

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

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

 

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

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

 

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

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

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

 

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

 


 

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


 

그리고 선분 1을 지운다.


 

다음은 선분 4,


 

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


 

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

 


입력형식

입력은 두 줄로 이뤄진다. 첫 줄은 꼭지점 N의 개수이며, 다음 줄부터는 선분의 연산자 정보와 선분 사이에 연결된 꼭지점이 가진 숫자가 번갈아 가며 나온다. 선분은 번호가 낮은 순이다. t는 더하기를, x는 곱하기를 의미한다. 앞의 폴리곤을 의미하는 입력 자료는 아래와 같다. 선분 1부터 시작하여 t, t, x, x사이에 그 사이에 연결된 꼭지점이 갖고 있는 수가 나옴을 알 수 있다.

<제약사항> 1. 3≤N≤50 2. 어떤 연산을 수행하더라도 꼭지점에 있는 수는 -32,768에서 32,767 사이에 있다.


출력형식

폴리곤에서 낼 수 있는 최고 점수를 출력한다.


입력 예

4 
t -7 t 4 x 2 x 5

출력 예

33


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP