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("10 9 3"); //1 2 6 //ルールを満たす御菓子の組み合わせは //(1円,2円,6円) //(1円,3円,5円) //(2円,3円,4円) //の3つがありますが、 //このうち辞書順が最小になる(1円,2円,6円)の組み合わせが答えになります。 } else if (InputPattern == "Input2") { WillReturn.Add("10 9 4"); //-1 //残念ながら直樹くんは御菓子を買うことができませんでした・・・ } else if (InputPattern == "Input3") { WillReturn.Add("30 40 4"); //1 2 7 30 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List InputList = GetInputList(); int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray(); int N = wkArr[0]; int D = wkArr[1]; int K = wkArr[2]; //[御菓子の数,金額合計]までの辞書式最小パスの2次元配列 string[,] CurrDP = new string[K + 1, D + 1]; string[,] PrevDP = new string[K + 1, D + 1]; PrevDP[0, 0] = ""; //初期化 string AnswerPath = null; for (int LoopN = 1; LoopN <= N; LoopN++) { Array.Copy(PrevDP, CurrDP, PrevDP.Length); for (int LoopK = 0; LoopK <= K - 1; LoopK++) { for (int LoopD = 0; LoopD <= D; LoopD++) { if (PrevDP[LoopK, LoopD] == null) continue; int NewIndK = LoopK + 1; int NewIndD = LoopD + LoopN; if (NewIndD > D) continue; string NewPath = PrevDP[LoopK, LoopD] + " " + LoopN.ToString().PadLeft(3, '0'); if (CurrDP[NewIndK, NewIndD] == null || CurrDP[NewIndK, NewIndD].CompareTo(NewPath) > 0) { CurrDP[NewIndK, NewIndD] = NewPath; } } } //Console.WriteLine(new string('■',15)); //Console.WriteLine("{0}円の御菓子までのDPの結果", LoopN); //PrintDP(CurrDP); //辞書順最小パスの更新 if (CurrDP[K, D] != null) { AnswerPath = CurrDP[K, D]; } Array.Copy(CurrDP, PrevDP, CurrDP.Length); } if (AnswerPath != null) { int[] AnswerIntArr = AnswerPath.Trim().Split(' '). Select(X => int.Parse(X)).ToArray(); string[] AnswerStrArr = Array.ConvertAll(AnswerIntArr, X => X.ToString()); Console.WriteLine(string.Join(" ", AnswerStrArr)); } else Console.WriteLine(-1); } static void PrintDP(string[,] pCurrDP) { var sb = new System.Text.StringBuilder(); for (int LoopK = 0; LoopK <= pCurrDP.GetUpperBound(0); LoopK++) { for (int LoopD = 0; LoopD <= pCurrDP.GetUpperBound(1); LoopD++) { if (pCurrDP[LoopK, LoopD] == null) continue; sb.AppendFormat("{0}個で{1}円の辞書順最小パスは{2}", LoopK, LoopD, pCurrDP[LoopK, LoopD]); sb.AppendLine(); } } Console.WriteLine(sb.ToString()); } }