ABC266-D Snuke Panic (1D)

問題へのリンク

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");
            WillReturn.Add("1 0 100");
            WillReturn.Add("3 3 10");
            WillReturn.Add("5 4 1");
            //101
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("1 4 1");
            WillReturn.Add("2 4 1");
            WillReturn.Add("3 4 1");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("1 4 602436426");
            WillReturn.Add("2 1 623690081");
            WillReturn.Add("3 3 262703497");
            WillReturn.Add("4 4 628894325");
            WillReturn.Add("5 3 450968417");
            WillReturn.Add("6 1 161735902");
            WillReturn.Add("7 1 707723857");
            WillReturn.Add("8 2 802329211");
            WillReturn.Add("9 0 317063340");
            WillReturn.Add("10 2 125660016");
            //2978279323
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct XAInfoDef
    {
        internal long X;
        internal long A;
    }

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

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

        var TDict = new Dictionary<long, XAInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long T = wkArr[0];
            long X = wkArr[1];
            long A = wkArr[2];
            XAInfoDef WillAdd;
            WillAdd.X = X;
            WillAdd.A = A;
            TDict[T] = WillAdd;
        }

        // 最大スコア[現在位置]なDP表
        long UB = 4;
        long?[] PrevDP = new long?[UB + 1];
        PrevDP[0] = 0;

        long KeysMax = TDict.Keys.Max();
        for (long I = 1; I <= KeysMax; I++) {
            long?[] CurrDP = new long?[UB + 1];
            for (long J = 0; J <= UB; J++) {
                if (PrevDP[J].HasValue == false) continue;

                Action<long> UpdateAct = (pNewJ) =>
                {
                    if (pNewJ < 0 || UB < pNewJ) return;

                    long AddScore = 0;
                    if (TDict.ContainsKey(I)) {
                        if (TDict[I].X == pNewJ) {
                            AddScore = TDict[I].A;
                        }
                    }
                    long NewVal = PrevDP[J].Value + AddScore;

                    if (CurrDP[pNewJ].HasValue) {
                        if (CurrDP[pNewJ] >= NewVal) {
                            return;
                        }
                    }
                    CurrDP[pNewJ] = NewVal;
                };

                UpdateAct(J - 1);
                UpdateAct(J);
                UpdateAct(J + 1);
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP.Max());
    }
}

解説

最大スコア[現在位置]でDPしてます。
状態数は5通りで、Nの上限も10の5乗なので間に合います。

コンテストでは、
DictionaryのKeysに対して、LINQのMaxメソッドを
For文で何度も使用してたのが原因で、TLEを連発したので
覚えておく