A21 Block Game

問題へのリンク

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("4 20");
            WillReturn.Add("3 30");
            WillReturn.Add("2 40");
            WillReturn.Add("1 10");
            //60
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8");
            WillReturn.Add("8 100");
            WillReturn.Add("7 100");
            WillReturn.Add("6 100");
            WillReturn.Add("5 100");
            WillReturn.Add("4 100");
            WillReturn.Add("3 100");
            WillReturn.Add("2 100");
            WillReturn.Add("1 100");
            //400
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PAInfoDef
    {
        internal int P;
        internal int A;
    }
    static List<PAInfoDef> mPAInfoList = new List<PAInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);
        int UB = N - 1;

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PAInfoDef WillAdd;
            WillAdd.P = wkArr[0] - 1;
            WillAdd.A = wkArr[1];
            mPAInfoList.Add(WillAdd);
        }

        // 最大スコア[状態]なDP表
        var PrevDP = new Dictionary<int, int>();
        JyoutaiDef FirstJyoutai;
        FirstJyoutai.LeftRemoveCnt = FirstJyoutai.RightRemoveCnt = 0;
        PrevDP[GetHash(FirstJyoutai)] = 0;

        for (int I = 1; I <= N; I++) {
            var CurrDP = new Dictionary<int, int>();

            foreach (var EachPair in PrevDP) {
                JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);

                JyoutaiDef NextJyoutai;

                // 現在の区間を求める
                int RangeSta = 0 + CurrJyoutai.LeftRemoveCnt;
                int RangeEnd = UB - CurrJyoutai.RightRemoveCnt;

                // 先頭を削除の場合
                NextJyoutai.LeftRemoveCnt = CurrJyoutai.LeftRemoveCnt + 1;
                NextJyoutai.RightRemoveCnt = CurrJyoutai.RightRemoveCnt;
                int PVal1 = mPAInfoList[RangeSta].P;
                int NewVal1 = EachPair.Value;
                if (RangeSta + 1 <= PVal1 && PVal1 <= RangeEnd) {
                    NewVal1 += mPAInfoList[RangeSta].A;
                }
                int Hash1 = GetHash(NextJyoutai);
                bool WillUpdate1 = true;
                if (CurrDP.ContainsKey(Hash1)) {
                    if (CurrDP[Hash1] >= NewVal1) {
                        WillUpdate1 = false;
                    }
                }
                if (WillUpdate1) {
                    CurrDP[Hash1] = NewVal1;
                }

                // 末尾を削除の場合
                NextJyoutai.LeftRemoveCnt = CurrJyoutai.LeftRemoveCnt;
                NextJyoutai.RightRemoveCnt = CurrJyoutai.RightRemoveCnt + 1;
                int PVal2 = mPAInfoList[RangeEnd].P;
                int NewVal2 = EachPair.Value;
                if (RangeSta <= PVal2 && PVal2 <= RangeEnd - 1) {
                    NewVal2 += mPAInfoList[RangeEnd].A;
                }
                int Hash2 = GetHash(NextJyoutai);
                bool WillUpdate2 = true;
                if (CurrDP.ContainsKey(Hash2)) {
                    if (CurrDP[Hash2] >= NewVal2) {
                        WillUpdate2 = false;
                    }
                }
                if (WillUpdate2) {
                    CurrDP[Hash2] = NewVal2;
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP.Values.Max());
    }

    struct JyoutaiDef
    {
        internal int LeftRemoveCnt;
        internal int RightRemoveCnt;
    }

    // ハッシュ値を求める
    static int GetHash(JyoutaiDef pJyoutai)
    {
        return pJyoutai.LeftRemoveCnt * 10000 + pJyoutai.RightRemoveCnt;
    }

    // ハッシュ値から状態を求める
    static JyoutaiDef GetJyoutai(int pHash)
    {
        JyoutaiDef WillReturn;
        WillReturn.LeftRemoveCnt = pHash / 10000;
        WillReturn.RightRemoveCnt = pHash % 10000;
        return WillReturn;
    }
}

解説

区間DPで解いてます。