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("6"); WillReturn.Add("3 2"); //12 //操作 レポートの文字列 クリップボードの文字列 //始めの状態 A 空 //コピー A A //ペースト AA A //コピー AA AA //ペースト AAAA AA //ペースト AAAAAA AA //コピーを2回、ペーストを3回行ったので合計のコストは12です。 //また、コピー、ペースト、ペースト、コピー、ペーストでも //12のコストで6文字作ることができます。 } else if (InputPattern == "Input2") { WillReturn.Add("10"); WillReturn.Add("1 3"); //15 //コピー、ペースト、コピー、ペースト、コピー、ペースト、ペーストで //12文字をコスト15で作れます。 //他にもコスト15で10文字以上作る方法があります。 } else if (InputPattern == "Input3") { WillReturn.Add("100"); WillReturn.Add("1000 1"); //1099 //コピーの後ペーストを99回行います } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List InputList = GetInputList(); int[] wkArr = { }; Action SplitAct = pStr => wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray(); SplitAct(InputList[0]); int N = wkArr[0]; SplitAct(InputList[1]); int C = wkArr[0]; int V = wkArr[1]; //最小コスト[状態のハッシュ値]なDP表 var PrevDP = new Dictionary(); PrevDP.Add(100000, 0); int Answer = int.MaxValue; while (true) { bool WillBreak = true; var CurrDP = new Dictionary(); foreach (var EachPair in PrevDP) { JyoutaiDef CurrJyoutai = DeriveJyoutai(EachPair.Key); //下限値枝切り if (EachPair.Value >= Answer) continue; if (CurrJyoutai.ReportLen >= N) { Answer = EachPair.Value; continue; } WillBreak = false; JyoutaiDef NewJyoutai; long NewKey; int NewValue; //コピーする場合 if (CurrJyoutai.ClipLen < CurrJyoutai.ReportLen) { NewJyoutai.ReportLen = CurrJyoutai.ReportLen; NewJyoutai.ClipLen = CurrJyoutai.ReportLen; NewKey = DeriveHash(NewJyoutai); NewValue = EachPair.Value + C; if (CurrDP.ContainsKey(NewKey) == false || CurrDP[NewKey] > NewValue) { CurrDP[NewKey] = NewValue; } } //ペーストする場合 if (CurrJyoutai.ClipLen > 0) { NewJyoutai.ReportLen = CurrJyoutai.ReportLen + CurrJyoutai.ClipLen; if (NewJyoutai.ReportLen > N) NewJyoutai.ReportLen = N; NewJyoutai.ClipLen = CurrJyoutai.ClipLen; NewKey = DeriveHash(NewJyoutai); NewValue = EachPair.Value + V; if (CurrDP.ContainsKey(NewKey) == false || CurrDP[NewKey] > NewValue) { CurrDP[NewKey] = NewValue; } } } PrevDP = CurrDP; if (WillBreak) break; } Console.WriteLine(Answer); } struct JyoutaiDef { internal int ReportLen; internal int ClipLen; } //上位5桁がClipLenで、下位5桁がReportLen static long DeriveHash(JyoutaiDef pJyoutai) { long WillReturn = 0; WillReturn += pJyoutai.ClipLen; WillReturn += (long)pJyoutai.ReportLen * 100000; return WillReturn; } static JyoutaiDef DeriveJyoutai(long pHash) { JyoutaiDef WillReturn; WillReturn.ClipLen = (int)(pHash % 100000); WillReturn.ReportLen = (int)(pHash / 100000); return WillReturn; } }