ID 만들기 > 문제은행

본문 바로가기


문제은행

1090 : ID 만들기

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 14 회    시도횟수: 59 회   



농부 창호는 소를 가지고 있는데, 이 소들은 ID들을 가지고 있다.
이 ID들은 M의 길이를 가지며(1≤M≤2,000) N개의(1≤N≤26) 서로 다른 소문자로 구성되어 있다.

 

우리는 이 ID를 편집해서 앞에서부터 읽으나 뒤에서부터 읽으나 같은(회문) ID로 보이도록 만들고자 한다.

 

ID의 어떠한 위치에라도 소문자들을 추가할 수도 있고 제거할 수도 있는데, 각각 소문자별로 추가하거나 삭제하는데 드는 비용이 모두 다르다.

 

우리는 이 비용을 최소화하면서 회문을 만들 때 최소 비용이 얼마인지 알려주는 프로그램을 작성하라.


첫 번째 줄에는 N과 M이 주어진다. 그 다음 두 번째 줄에는 ID가 주어진다. 세 번째 줄부터 N+2개의 줄에는 각각의 줄에 소문자, 해당 소문자의 추가비용, 해당 소문자의 삭제 비용이 순서대로 주어진다.



주어진 ID를 가지고 회문을 만들 경우에 소요되는 최소비용을 출력한다.


[Copy]
3 4 
abcb 
a 1000 1100 
b 350 700 
c 200 800
[Copy]
900





USACO 2007 Open Gold Cheapest Palindrome, poj 3280

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.