using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "Input5"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("4"); WillReturn.Add("1 2 3 4"); } else if (InputPattern == "Input2") { WillReturn.Add("4"); WillReturn.Add("5 4 4 9"); } else if (InputPattern == "Input3") { WillReturn.Add("7"); WillReturn.Add("1 2 9 10 1 1 4"); } else if (InputPattern == "Input4") { WillReturn.Add("1"); WillReturn.Add("100"); } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct JyoutaiDef { internal int CurrP; internal int SumVal; } static void Main() { List InputList = GetInputList(); int[] VArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray(); int UB = VArr.GetUpperBound(0); var stk = new Stack(); JyoutaiDef WillPush; WillPush.CurrP = 0; WillPush.SumVal = 0; stk.Push(WillPush); int Answer = 0; //メモ化探索用 var MemoDict = new Dictionary(); while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); if (Answer < Popped.SumVal) Answer = Popped.SumVal; for (int I = Popped.CurrP; I <= UB && I <= Popped.CurrP + 1; I++) { WillPush.CurrP = I + 2; WillPush.SumVal = Popped.SumVal + VArr[I]; if (MemoDict.ContainsKey(WillPush.CurrP)) { if (MemoDict[WillPush.CurrP] >= WillPush.SumVal) continue; } MemoDict[WillPush.CurrP] = WillPush.SumVal; stk.Push(WillPush); } } Console.WriteLine(Answer); } }