AOJ 0615 ケーキの切り分け2

問題へのリンク(AOJ)
問題へのリンク(AtCoder)

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");
            WillReturn.Add("2");
            WillReturn.Add("8");
            WillReturn.Add("1");
            WillReturn.Add("10");
            WillReturn.Add("9");
            //18
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8");
            WillReturn.Add("1");
            WillReturn.Add("10");
            WillReturn.Add("4");
            WillReturn.Add("5");
            WillReturn.Add("6");
            WillReturn.Add("2");
            WillReturn.Add("9");
            WillReturn.Add("3");
            //26
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15");
            WillReturn.Add("182243672");
            WillReturn.Add("10074562");
            WillReturn.Add("977552215");
            WillReturn.Add("122668426");
            WillReturn.Add("685444213");
            WillReturn.Add("3784162");
            WillReturn.Add("463324752");
            WillReturn.Add("560071245");
            WillReturn.Add("134465220");
            WillReturn.Add("21447865");
            WillReturn.Add("654556327");
            WillReturn.Add("183481051");
            WillReturn.Add("20041805");
            WillReturn.Add("405079805");
            WillReturn.Add("564327789");
            //3600242976
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long[] mAArr;
    static long UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mAArr = InputList.Skip(1).Select(pX => long.Parse(pX)).ToArray();
        UB = mAArr.GetUpperBound(0);

        if (mAArr.Length <= 2) {
            Console.WriteLine(mAArr.Max());
            return;
        }

        long RestCnt = mAArr.Length;

        var AnswerList = new List<long>();
        for (long I = 0; I <= UB; I++) {
            long Ind1 = AdjustInd(I - 1);
            long Ind2 = AdjustInd(I + 1);
            ExecAiteTurn(ref Ind1, ref Ind2);
            AnswerList.Add(mAArr[I] + dfs(Ind1, Ind2, RestCnt - 2));
        }
        Console.WriteLine(AnswerList.Max());
    }

    static Dictionary<long, long> mMemo = new Dictionary<long, long>();

    static long dfs(long pInd1, long pInd2, long pRestCnt)
    {
        if (pRestCnt <= 0) return 0;

        long Hash = 0;
        Hash += pInd1; Hash *= 10000;
        Hash += pInd2; Hash *= 10000;
        Hash += pRestCnt;

        if (mMemo.ContainsKey(Hash)) {
            return mMemo[Hash];
        }

        var KouhoList = new List<long>();

        Action<long, long, long> TakeAct = (pTakeVal, pNewInd1, pNewInd2) =>
        {
            long KouhoVal = pTakeVal;
            ExecAiteTurn(ref pNewInd1, ref pNewInd2);
            KouhoVal += dfs(pNewInd1, pNewInd2, pRestCnt - 2);
            KouhoList.Add(KouhoVal);
        };

        // 左を取る場合
        TakeAct(mAArr[pInd1], AdjustInd(pInd1 - 1), pInd2);

        // 右を取る場合
        TakeAct(mAArr[pInd2], pInd1, AdjustInd(pInd2 + 1));

        return mMemo[Hash] = KouhoList.Max();
    }

    // 相手の1回の行動分、Indを動かす
    static void ExecAiteTurn(ref long pInd1, ref long pInd2)
    {
        if (mAArr[pInd1] <= mAArr[pInd2]) {
            pInd2++;
        }
        else {
            pInd1--;
        }

        pInd1 = AdjustInd(pInd1);
        pInd2 = AdjustInd(pInd2);
    }

    // インデックスの調整
    static long AdjustInd(long pInd)
    {
        if (pInd > UB) {
            pInd %= (UB + 1);
        }
        if (pInd < 0) {
            pInd += (UB + 1);
        }
        return pInd;
    }
}

解説

メモ化再帰で解いてます。
状態数は、2000 Choose 2なため、間に合います。