第3回PAST H ハードル走

問題へのリンク

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("2 5");
            WillReturn.Add("1 4");
            WillReturn.Add("2 2 20");
            //10
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 5");
            WillReturn.Add("1 2 3 4");
            WillReturn.Add("2 20 100");
            //164
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 19");
            WillReturn.Add("1 3 4 5 7 8 10 13 15 17");
            WillReturn.Add("2 1000 10");
            //138
        }
        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(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        int L = wkArr[1];
        int UB = L;

        var XSet = new HashSet<int>();
        XSet.UnionWith(InputList[1].Split(' ').Select(pX => int.Parse(pX)));

        SplitAct(InputList[2]);
        int T1 = wkArr[0];
        int T2 = wkArr[1];
        int T3 = wkArr[2];

        // 最小分数[現在位置]なDP表
        long?[] DPArr = new long?[UB + 1];
        DPArr[0] = 0;

        for (int I = 0; I <= UB - 1; I++) {
            if (DPArr[I].HasValue == false) continue;

            Action<int, long> UpdateAct = (pNewInd, pNewVal) =>
            {
                if (DPArr[pNewInd].HasValue) {
                    if (DPArr[pNewInd].Value <= pNewVal) {
                        return;
                    }
                }
                DPArr[pNewInd] = pNewVal;
            };

            // 経路1 1進む場合
            long NewVal1 = DPArr[I].Value + T1;
            if (XSet.Contains(I)) {
                NewVal1 += T3;
            }
            UpdateAct(I + 1, NewVal1);

            // 経路2 ジャンプで2進む場合
            int JumpKyori2 = Math.Min(2, L - I);
            long NewVal2 = DPArr[I].Value + (T1 + T2) * JumpKyori2 / 2;
            if (XSet.Contains(I)) {
                NewVal2 += T3;
            }
            UpdateAct(I + JumpKyori2, NewVal2);

            // 経路3 ジャンプで4進む場合
            int JumpKyori3 = Math.Min(4, L - I);
            long NewVal3 = DPArr[I].Value;
            if (JumpKyori3 == 4) {
                NewVal3 += T1 + 3 * T2;
            }
            else {
                NewVal3 += T1 / 2 + T2 / 2 + T2 * (JumpKyori3 - 1);
            }
            if (XSet.Contains(I)) {
                NewVal3 += T3;
            }
            UpdateAct(I + JumpKyori3, NewVal3);

            //Console.WriteLine("{0}回目のDP結果", I);
            //for (int J = 0; J <= UB; J++) {
            //    Console.WriteLine("DPArr[{0}]={1}", J, DPArr[J]);
            //}
        }
        Console.WriteLine(DPArr[UB]);
    }
}

解説

動的計画法で解いてます。