Educational DP Contest L Deque

問題へのリンク

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("4");
            WillReturn.Add("10 80 90 30");
            //10
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("10 100 10");
            //-80
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1");
            WillReturn.Add("10");
            //10
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10");
            WillReturn.Add("1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1");
            //4999999995
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("6");
            WillReturn.Add("4 2 9 7 1 5");
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] mAArr;
    static long UB;

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

        long Result = DFS(0, UB);
        Console.WriteLine(Result);
    }

    // メモ化再帰で解く
    static Dictionary<long, long> mMemoDict = new Dictionary<long, long>();
    static long DFS(long pFrontInd, long pRearInd)
    {
        long Hash = pFrontInd * 10000 + pRearInd;
        if (mMemoDict.ContainsKey(Hash)) {
            return mMemoDict[Hash];
        }

        // 先手番か後手番かを求める
        long DiffSum = pFrontInd + (UB - pRearInd);
        bool IsSente = (DiffSum % 2 == 0);

        if (pFrontInd > pRearInd) {
            return 0;
        }

        var SeniList = new List<long>();

        // 先頭から取る場合
        long Result1 = DFS(pFrontInd + 1, pRearInd);
        if (IsSente) Result1 += mAArr[pFrontInd];
        else Result1 -= mAArr[pFrontInd];
        SeniList.Add(Result1);

        // 末尾から取る場合
        long Result2 = DFS(pFrontInd, pRearInd - 1);
        if (IsSente) Result2 += mAArr[pRearInd];
        else Result2 -= mAArr[pRearInd];
        SeniList.Add(Result2);

        if (IsSente) return mMemoDict[Hash] = SeniList.Max();
        return mMemoDict[Hash] = SeniList.Min();
    }
}

解説

先手の得点 - 後手の得点 をSとおいて
先手はSを最大化しようとして
後手はSを最小化しようとします。

後は、メモ化再帰で
先手は遷移可能な状態からSが最大の状態を選び
後手は遷移可能な状態からSが最小の状態を選ぶ
ようにします。

類題

TDP B ゲーム