using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("4"); WillReturn.Add("1 2 3 4"); //6 //お寿司の取り方は、 //「1個目と3個目」のお寿司を取る、 //「1個目と4個目」のお寿司を取る、 //または「2個目と4個目」のお寿司を取る方法があるが、 //2個目、4個目のお寿司を取ることで、最大の美味しさが得られる。 } else if (InputPattern == "Input2") { WillReturn.Add("4"); WillReturn.Add("5 4 4 9"); //14 //1個目のお寿司と4個目のお寿司を取ることで //最大の美味しさの合計が得られる。 } else if (InputPattern == "Input3") { WillReturn.Add("7"); WillReturn.Add("1 2 9 10 1 1 4"); //2,10,4と取れば最大の16が得られる。 //10の後の6番目の1をあえてスルーしないといけない。 } else if (InputPattern == "Input4") { WillReturn.Add("1"); WillReturn.Add("100"); //100 //1皿しかない場合もあります。 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List InputList = GetInputList(); int[] VArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray(); int UB = VArr.GetUpperBound(0); //美味しさ合計の最大値[皿の合計]のDP表 int[] DPArr = new int[UB + 1]; for (int I = 0; I <= UB; I++) { if (I == 0 || I == 1) { DPArr[I] = VArr[I]; continue; } //配列の添字の上限までの範囲での、最大値を返す Func DeriveHaniMaxFunc = pJyougenInd => { int WillReturn = DPArr[0]; for (int J = 0; J <= pJyougenInd; J++) { if (WillReturn < DPArr[J]) WillReturn = DPArr[J]; } return WillReturn; }; //その皿を取るノードでの美味しさ合計の最大値 int Node1SumV = DeriveHaniMaxFunc(I - 2) + VArr[I]; //その皿を取らないノードでの美味しさ合計の最大値 int Node2SumV = DeriveHaniMaxFunc(I - 1); DPArr[I] = Math.Max(Node1SumV, Node2SumV); } Console.WriteLine(DPArr.Max()); } }