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 = ""; 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) { //添字が長さの合計、値が最小の枚数 int UB = NeedLenArr.Max(); Nullable[] ItaCntArr = new Nullable[UB + 1]; //初期設定 ItaCntArr[0] = 0; foreach (int EachLen in pLenCombiArr) { for (int I = 0; I <= UB; I++) { //123ナップサックなのでリバースループしない //長さの和を求める if (ItaCntArr[I] == null) continue; int wkSumLen = I + EachLen; if (wkSumLen > UB) break; //枚数の和を求める int wkSumCnt = (ItaCntArr[I] ?? 0) + 1; //枚数の最小値で更新可能かを判定 if (ItaCntArr[wkSumLen] == null || ItaCntArr[wkSumLen] > wkSumCnt) { ItaCntArr[wkSumLen] = wkSumCnt; } } } pFoundAnswer = Array.TrueForAll(NeedLenArr, X => ItaCntArr[X] != null); pMinItaCnt = NeedLenArr.Sum(X => ItaCntArr[X] ?? 0); } }