AOJ 0611 シルクロード

問題へのリンク

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("3 5");
            WillReturn.Add("10");
            WillReturn.Add("25");
            WillReturn.Add("15");
            WillReturn.Add("50");
            WillReturn.Add("30");
            WillReturn.Add("15");
            WillReturn.Add("40");
            WillReturn.Add("30");
            //1125
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 6");
            WillReturn.Add("99");
            WillReturn.Add("20");
            WillReturn.Add("490");
            WillReturn.Add("612");
            WillReturn.Add("515");
            WillReturn.Add("131");
            WillReturn.Add("931");
            WillReturn.Add("1000");
            //31589
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long N = wkArr[0];
        long M = wkArr[1];

        // ゴールノード
        long GoalNode = N;

        // 待機回数の上限
        long WaitLimit = M - N;

        var DistanceList = new List<long>();
        foreach (string EachStr in InputList.Skip(1).Take((int)N)) {
            DistanceList.Add(long.Parse(EachStr));
        }

        var WeatherList = new List<long>();
        foreach (string EachStr in InputList.Skip(1 + (int)N)) {
            WeatherList.Add(long.Parse(EachStr));
        }

        // コスト[現在ノード,休んだ回数]なDP表
        var PrevDP = new Dictionary<long, long>();
        JyoutaiDef FirstJyoutai;
        FirstJyoutai.Pos = 0;
        FirstJyoutai.WaitCnt = 0;
        PrevDP[GetHash(FirstJyoutai)] = 0;

        var AnswerList = new List<long>();
        foreach (long EachWeather in WeatherList) {
            var CurrDP = new Dictionary<long, long>();
            foreach (var EachPair in PrevDP) {
                Action<JyoutaiDef, long> UpdateAct = (pNewJyoutai, pNewVal) =>
                {
                    long Hash = GetHash(pNewJyoutai);
                    if (CurrDP.ContainsKey(Hash)) {
                        if (CurrDP[Hash] <= pNewVal) {
                            return;
                        }
                    }
                    CurrDP[Hash] = pNewVal;
                };

                // 移動する場合
                JyoutaiDef CurrJyoutai1 = GetJyoutai(EachPair.Key);
                long CurrDistance = DistanceList[(int)CurrJyoutai1.Pos];
                CurrJyoutai1.Pos++;
                long NewVal = EachPair.Value + CurrDistance * EachWeather;
                if (CurrJyoutai1.Pos == GoalNode) {
                    AnswerList.Add(NewVal);
                }
                else {
                    UpdateAct(CurrJyoutai1, NewVal);
                }

                // 待機する場合
                JyoutaiDef CurrJyoutai2 = GetJyoutai(EachPair.Key);
                CurrJyoutai2.WaitCnt++;
                if (CurrJyoutai2.WaitCnt <= WaitLimit) {
                    UpdateAct(CurrJyoutai2, EachPair.Value);
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(AnswerList.Min());
    }

    struct JyoutaiDef
    {
        internal long Pos;
        internal long WaitCnt;
    }

    static long GetHash(JyoutaiDef pJyoutai)
    {
        return pJyoutai.Pos * 100000000 + pJyoutai.WaitCnt;
    }

    static JyoutaiDef GetJyoutai(long pHash)
    {
        JyoutaiDef WillReturn;
        WillReturn.Pos = pHash / 100000000;
        WillReturn.WaitCnt = pHash % 100000000;
        return WillReturn;
    }
}

解説

コスト[現在ノード,休んだ回数]でDPしてます。
枝切り用で、休める上限を最初に求めてます。