폴리곤(Polygon) > 문제은행

본문 바로가기


실전대비 Level4

1321 : 폴리곤(Polygon)

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 17 회    시도횟수: 54 회   



폴리곤 게임은 다각형의 꼭지점과 선분을 이용하여 하는 1인용 게임이다. 게임은 한 다각형의 N개의 꼭지점에서 시작한다. 아래 그림은 N=4일 때의 예이다. 각각의 꼭지점은 임의의 정수를 갖고 있으며, 선분은 각각 +(덧셈)과 *(곱셈)이라는 정보를 가지고 있다. 모서리는 1부터 N까지 번호가 새겨져 있다.

 

게임을 시작하려면 가장 먼저 꼭지점을 연결하는 선분 중 아무 거나 하나를 없애야 한다. 그 다음부터 게임은 아래와 같이 진행된다.

 

한 선분 E와 그것이 연결하고 있는 두 꼭지점 V_1과 V_2를 선택한다. 다음, 이것들을 하나의 꼭지점으로 대체한다. 거기에 들어가는 숫자는 V_1과 V_2 꼭지점이 가진 수를 선분에 들어있던 연산자로 연산을 수행한 결과이다. 게임은 선분이 하나도 남지 않으면 끝난다. 그리고 점수는 마지막 남은 꼭지점에든 수이다.

 

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

 

e3050b66a1b29a01767400d7560a4131_1449730
 

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

e3050b66a1b29a01767400d7560a4131_1449730
 

그리고 선분 1을 지운다.

e3050b66a1b29a01767400d7560a4131_1449730
 

다음은 선분 4,

e3050b66a1b29a01767400d7560a4131_1449730
 

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

e3050b66a1b29a01767400d7560a4131_1449730
 

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


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

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



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


[Copy]
4 
t -7 t 4 x 2 x 5
[Copy]
33



출처 : IOI 1998 day2


IOI 1998 day2 Polygon, poj 1179

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.