No.555 世界史のレポート

■■■問題■■■

addeight君は今、世界史のレポートをパソコンで書いています。

しかし、彼は世界史が苦手で、レポートにはまだアルファベットのAしか書かれていません。
レポートにはN文字以上書かれてないと、世界史の怖い先生に怒られてしまいます。

そこで、addeight君はコピーとペーストだけでN文字以上の文字列を作ることにしました。
コピーをするとレポートのすべての文字列がクリップボードにコピーされ、
ペーストをするとレポートの文字列の後ろにクリップボードの文字列が追加されます。

コピー、ペーストにはそれぞれC,Vだけコストがかかります。
N文字以上作る最小のコストを求めてください。

クリップボードの初期状態は、空文字列です。

■■■入力■■■

N
C V

●2 <= N <= 5万
●1 <= C,V <= 1000

■■■出力■■■

N文字以上作るのにかかる最小のコストを出力してください。
最後に改行してください。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        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<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> 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<long, int>();
        PrevDP.Add(100000, 0);

        int Answer = int.MaxValue;

        while (true) {
            bool WillBreak = true;
            var CurrDP = new Dictionary<long, int>();

            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;
    }
}

解説

最小のコスト[レポートの文字数,クリップボートの文字数]を更新する動的計画法で解いてます。