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("28 29 30 30"); //4 //A=28が1枚,B=29が1枚,C=30が2枚の計4枚必要 } else if (InputPattern == "Input2") { WillReturn.Add("2 3 7 15"); //6 //A=2が3枚,B=3が2枚,C=15が1枚の計6枚必要。 //7はAを2枚、Bを1枚でつなげて作れば良い。 } else if (InputPattern == "Input3") { WillReturn.Add("3 6 11 20"); //5 } 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 = ""; foreach (int[] EachCombiArr in LenCombiArrList) { bool FoundAnswer; int MinItaCnt; DeriveNeedMinCnt(EachCombiArr, out FoundAnswer, out MinItaCnt); if (FoundAnswer == false) continue; if (AnswerCnt < MinItaCnt) continue; AnswerCnt = MinItaCnt; AnswerItaCombi = ""; Array.ForEach(EachCombiArr, X => AnswerItaCombi += X.ToString() + ","); } Console.WriteLine(AnswerCnt); //Console.WriteLine("ABCの板の長さは{0}", AnswerItaCombi); } //長さの組み合わせを求める static List DeriveLenCombiArrList(int pMaxLen) { var WillReturn = new List(); for (int A = 1; A <= pMaxLen; A++) { for (int B = A; B <= pMaxLen; B++) { for (int C = B; C <= pMaxLen; C++) { var wkList = new int[] { A, B, C }; int[] WillAdd = wkList.Distinct().ToArray(); WillReturn.Add(WillAdd); } } } return WillReturn; } //4つの長さを満たす、最小の板の枚数を動的計画法で求める static void DeriveNeedMinCnt(int[] pLenCombiArr, out bool pFoundAnswer, out int pMinItaCnt) { //最小の枚数[長さの合計]なDP表 int UB = NeedLenArr.Max(); Nullable[] DPArr = new Nullable[UB + 1]; //初期設定 DPArr[0] = 0; foreach (int EachLen in pLenCombiArr) { for (int I = 0; I <= UB; I++) { //123ナップサックなのでリバースループしない //長さの和を求める if (DPArr[I] == null) continue; int wkSumLen = I + EachLen; if (wkSumLen > UB) break; //枚数の和を求める int wkSumCnt = DPArr[I].Value + 1; //枚数の最小値で更新可能かを判定 if (DPArr[wkSumLen] == null || DPArr[wkSumLen] > wkSumCnt) { DPArr[wkSumLen] = wkSumCnt; } } } pFoundAnswer = Array.TrueForAll(NeedLenArr, X => DPArr[X] != null); pMinItaCnt = NeedLenArr.Sum(X => DPArr[X] ?? 0); } }