AOJ 0530 ぴょんぴょん川渡り

問題へのリンク

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("5 1");
            WillReturn.Add("2 1 3 2 2");
            WillReturn.Add("1 3 2");
            WillReturn.Add("1 1 7");
            WillReturn.Add("1 2 1");
            WillReturn.Add("1 4 4");
            WillReturn.Add("5 0");
            WillReturn.Add("2 1 3 2 2");
            WillReturn.Add("1 3 2");
            WillReturn.Add("1 1 7");
            WillReturn.Add("1 2 1");
            WillReturn.Add("1 4 4");
            WillReturn.Add("0 0");
            //17
            //40
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 3");
            WillReturn.Add("0");
            WillReturn.Add("9 150 471 313 513 367 694 379 555 404 607 488 50 524 461 781 192 787 719");
            WillReturn.Add("9 151 267 194 837 205 985 327 544 401 531 679 117 684 714 827 960 887 57");
            WillReturn.Add("9 29 18 113 542 156 625 166 123 292 774 360 637 630 317 918 861 941 76");
            WillReturn.Add("10 118 312 177 326 303 25 343 585 497 655 772 525 833 270 843 243 914 886 988 730");
            WillReturn.Add("9 76 625 138 944 350 226 387 682 546 918 685 65 780 280 859 849 987 196");
            WillReturn.Add("0 0");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        long CurrInd = 0;
        while (true) {
            SplitAct(InputList[(int)CurrInd]);
            long N = wkArr[0];
            long M = wkArr[1];
            if (N == 0 && M == 0) break;

            string[] InputArr = InputList.Skip((int)CurrInd + 1).Take((int)N).ToArray();
            Solve(N, M, InputArr);

            CurrInd += 1 + N;
        }
    }

    struct ShimaInfoDef
    {
        internal long X;
        internal long CostVal;
    }

    static void Solve(long pMaxY, long pM, string[] pInputArr)
    {
        // 島情報のリスト[Y座標]なDict
        var ShimaListDict = new Dictionary<long, List<ShimaInfoDef>>();

        // コスト[座標のハッシュ値]
        var CostDict = new Dictionary<long, long>();

        for (long I = 0; I <= pInputArr.GetUpperBound(0); I++) {
            long CurrY = pMaxY - I;
            ShimaListDict[CurrY] = new List<ShimaInfoDef>();

            long[] wkArr = pInputArr[I].Split(' ').Select(pX => long.Parse(pX)).ToArray();

            for (long J = 1; J <= wkArr.GetUpperBound(0); J += 2) {
                ShimaInfoDef WillAdd;
                WillAdd.X = wkArr[J];
                WillAdd.CostVal = wkArr[J + 1];
                ShimaListDict[CurrY].Add(WillAdd);

                long PosHash = GetPosHash(WillAdd.X, CurrY);
                CostDict[PosHash] = WillAdd.CostVal;
            }
        }

        // 最小コスト[状態のハッシュ値]なDP表
        var PrevDP = new Dictionary<long, long>();
        JyoutaiDef FirstJyoutai;

        // 最初に、1つ飛びする場合
        foreach (ShimaInfoDef EachShimaInfo in ShimaListDict[1]) {
            FirstJyoutai.CurrX = EachShimaInfo.X;
            FirstJyoutai.CurrY = 1;
            FirstJyoutai.SkipCnt = 0;
            PrevDP[GetHash(FirstJyoutai)] = 0;
        }

        // 最初に、2つ飛びする場合
        if (pM >= 1) {
            foreach (ShimaInfoDef EachShimaInfo in ShimaListDict[2]) {
                FirstJyoutai.CurrX = EachShimaInfo.X;
                FirstJyoutai.CurrY = 2;
                FirstJyoutai.SkipCnt = 1;
                PrevDP[GetHash(FirstJyoutai)] = 0;
            }
        }

        var AnswerList = new List<long>();
        while (PrevDP.Count > 0) {
            var CurrDP = new Dictionary<long, long>();

            foreach (var EachPair in PrevDP) {
                JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);

                Action<long, long> UpdateAct = (pNewY, pNewSkipCnt) =>
                {
                    if (pNewSkipCnt > pM) return;

                    if (pNewY > pMaxY) {
                        AnswerList.Add(EachPair.Value);
                        return;
                    }

                    foreach (ShimaInfoDef EachShimaInfo in ShimaListDict[pNewY]) {
                        long CurrPosHash = GetPosHash(CurrJyoutai.CurrX, CurrJyoutai.CurrY);
                        long CurrCost = CostDict[CurrPosHash];

                        JyoutaiDef NewJyoutai;
                        NewJyoutai.CurrX = EachShimaInfo.X;
                        NewJyoutai.CurrY = pNewY;
                        NewJyoutai.SkipCnt = pNewSkipCnt;
                        long AddCost = EachShimaInfo.CostVal + CurrCost;
                        AddCost *= Math.Abs(CurrJyoutai.CurrX - NewJyoutai.CurrX);

                        long NewCost = EachPair.Value + AddCost;

                        long Hash = GetHash(NewJyoutai);
                        if (CurrDP.ContainsKey(Hash)) {
                            if (CurrDP[Hash] <= NewCost) {
                                continue;
                            }
                        }
                        CurrDP[Hash] = NewCost;
                    }
                };

                // 1つ飛ぶ場合
                UpdateAct(CurrJyoutai.CurrY + 1, CurrJyoutai.SkipCnt);

                // 2つ飛ぶ場合
                UpdateAct(CurrJyoutai.CurrY + 2, CurrJyoutai.SkipCnt + 1);
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(AnswerList.Min());
    }

    // 座標のハッシュ値を返す
    static long GetPosHash(long pX, long pY)
    {
        return pX * 10000 + pY;
    }

    struct JyoutaiDef
    {
        internal long CurrX;
        internal long CurrY;
        internal long SkipCnt; // 2つ飛びの回数
    }

    static long GetHash(JyoutaiDef pJyoutai)
    {
        long Hash = 0;
        Hash += pJyoutai.CurrX;
        Hash *= 10000;
        Hash += pJyoutai.CurrY;
        Hash *= 10000;
        Hash += pJyoutai.SkipCnt;
        return Hash;
    }

    static JyoutaiDef GetJyoutai(long pHash)
    {
        JyoutaiDef ReturnJyoutai;
        ReturnJyoutai.SkipCnt = pHash % 10000;
        pHash /= 10000;
        ReturnJyoutai.CurrY = pHash % 10000;
        pHash /= 10000;
        ReturnJyoutai.CurrX = pHash;
        return ReturnJyoutai;
    }
}

解説

最小コスト[状態のハッシュ値]でDPしてます。