using System; using System.Collections.Generic; using System.Linq; //YukiCoder No.555 世界史のレポート //https://yukicoder.me/problems/no/555 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("6"); WillReturn.Add("3 2"); //12 } else if (InputPattern == "Input2") { WillReturn.Add("10"); WillReturn.Add("1 3"); //15 } else if (InputPattern == "Input3") { WillReturn.Add("100"); WillReturn.Add("1000 1"); //1099 } else if (InputPattern == "Input4") { WillReturn.Add("35344"); WillReturn.Add("768 919"); //25141 } 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 (CurrJyoutai.ReportLen >= N) { if (Answer > EachPair.Value) 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; 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); ////最小コスト[レポートの文字数,クリップボートの文字数]なDP表 //var DPArr = new Nullable[N + 1, N + 1]; //DPArr[1, 0] = 0; //for (int I = 0; I <= N; I++) { // for (int J = 0; J <= N; J++) { // if (DPArr[I, J].HasValue == false) continue; // //コピーする場合 // int NewI = I; // int NewJ = I; // int NewCost = DPArr[I, J].Value + C; // if (NewI > N) NewI = N; // if (NewJ > N) NewJ = N; // if (DPArr[NewI, NewJ].HasValue == false // || DPArr[NewI, NewJ].Value > NewCost) { // DPArr[NewI, NewJ] = NewCost; // } // //ペーストする場合 // NewI = I + J; // NewJ = J; // NewCost = DPArr[I, J].Value + V; // if (NewI > N) NewI = N; // if (NewJ > N) NewJ = N; // if (DPArr[NewI, NewJ].HasValue == false // || DPArr[NewI, NewJ].Value > NewCost) { // DPArr[NewI, NewJ] = NewCost; // } // } //} ////for (int I = 0; I <= N; I++) { //// for (int J = 0; J <= N; J++) { //// Console.WriteLine("DPArr[{0},{1}]={2}", I, J, DPArr[I, J]); //// } ////} //int Answer = int.MaxValue; //for (int I = 0; I <= N; I++) { // if (DPArr[N, I].HasValue == false) continue; // if (Answer > DPArr[N, I].Value) // Answer = DPArr[N, I].Value; //} //Console.WriteLine(Answer); } struct JyoutaiDef { internal int ReportLen; internal int ClipLen; } 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; } }