using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/2591 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("3"); WillReturn.Add(")(((()"); WillReturn.Add("10 22 3 5 2 13"); //15 } else if (InputPattern == "Input2") { WillReturn.Add("4"); WillReturn.Add("()(()())"); WillReturn.Add("3141592 653589 793238 462643 38327 9502884 1971 69399375"); //0 } else if (InputPattern == "Input3") { WillReturn.Add("5"); WillReturn.Add("(((((((((("); WillReturn.Add("1 2 3 4 5 6 7 8 9 10"); //30 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List InputList = GetInputList(); char[] CharArr = InputList[1].ToCharArray(); long[] CostArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray(); long UB = CharArr.GetUpperBound(0); // コスト[括弧の深さ]なDP表 var PrevDP = new Dictionary(); PrevDP[0] = 0; for (long I = 0; I <= UB; I++) { var CurrDP = new Dictionary(); foreach (var EachPair in PrevDP) { Action UpdateAct = (pNewChar, pCost) => { long NewKey = EachPair.Key; if (pNewChar == ')') { if (--NewKey < 0) { return; } } else NewKey++; long NewVal = EachPair.Value + pCost; if (CurrDP.ContainsKey(NewKey)) { if (CurrDP[NewKey] <= NewVal) { return; } } CurrDP[NewKey] = NewVal; }; if (CharArr[I] == '(') { UpdateAct(')', CostArr[I]); UpdateAct('(', 0); } if (CharArr[I] == ')') { UpdateAct('(', CostArr[I]); UpdateAct(')', 0); } } PrevDP = CurrDP; } Console.WriteLine(PrevDP[0]); } }