using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "Input4"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("28 29 30 30"); } else if (InputPattern == "Input2") { WillReturn.Add("2 3 7 15"); } else if (InputPattern == "Input3") { WillReturn.Add("3 6 11 20"); } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } //必要な板の長さの配列 static int[] NeedLenArr; static void Main() { List InputList = GetInputList(); NeedLenArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray(); List LenCombiArrList = DeriveLenCombiArrList(NeedLenArr.Max()); int AnswerCnt = int.MaxValue; string AnswerItaCombi = ""; string AnswerLog = ""; foreach (int[] EachCombiArr in LenCombiArrList) { bool FoundAnswer; int MinItaCnt; string Log; DeriveNeedMinCnt(EachCombiArr, out FoundAnswer, out MinItaCnt, out Log); if (FoundAnswer == false) continue; if (AnswerCnt < MinItaCnt) continue; AnswerCnt = MinItaCnt; AnswerLog = Log; AnswerItaCombi = ""; Array.ForEach(EachCombiArr, X => AnswerItaCombi += X.ToString() + ","); } Console.WriteLine(AnswerCnt); //Console.WriteLine("ABCの板の長さは{0}", AnswerItaCombi); //Console.WriteLine(AnswerLog); } //長さの組み合わせを求める static List DeriveLenCombiArrList(int pMaxLen) { var WillReturn = new List(); for (int A = 1; A <= pMaxLen; A++) { for (int B = A + 1; B <= pMaxLen; B++) { for (int C = B + 1; C <= pMaxLen; C++) { WillReturn.Add(new int[] { A, B, C }); } } } return WillReturn; } struct JyoutaiDef { internal int CurrNeedLenP; internal int CurrItaP; internal int SumLen; internal int ItaCnt; internal string Log; } //4つの長さを満たす最小の板の枚数を深さ優先探索で求める static void DeriveNeedMinCnt(int[] pLenCombiArr, out bool pFoundAnswer, out int pMinItaCnt, out string pLog) { pFoundAnswer = false; pMinItaCnt = int.MaxValue; pLog = ""; var stk = new Stack(); JyoutaiDef WillPush; WillPush.CurrNeedLenP = 0; WillPush.CurrItaP = 0; WillPush.SumLen = 0; WillPush.ItaCnt = 0; WillPush.Log = ""; stk.Push(WillPush); while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); //クリア判定 if (Popped.SumLen == NeedLenArr[Popped.CurrNeedLenP]) { Popped.CurrNeedLenP++; if (Popped.CurrNeedLenP > NeedLenArr.GetUpperBound(0)) { pFoundAnswer = true; if (pMinItaCnt > Popped.ItaCnt) { pMinItaCnt = Popped.ItaCnt; pLog = Popped.Log; } continue; } Popped.CurrItaP = 0; Popped.SumLen = 0; } WillPush.ItaCnt = Popped.ItaCnt + 1; if (WillPush.ItaCnt + 1 >= pMinItaCnt) continue; for (int I = Popped.CurrItaP; I <= pLenCombiArr.GetUpperBound(0); I++) { WillPush.CurrNeedLenP = Popped.CurrNeedLenP; WillPush.CurrItaP = I; WillPush.SumLen = Popped.SumLen + pLenCombiArr[I]; if (WillPush.SumLen > NeedLenArr[Popped.CurrNeedLenP]) continue; WillPush.Log = Popped.Log + string.Format("長さ{0}の板。", pLenCombiArr[I]); stk.Push(WillPush); } } } }