AOJ 1611 ダルマ落とし

問題へのリンク

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("1 2 3 4");
            WillReturn.Add("4");
            WillReturn.Add("1 2 3 1");
            WillReturn.Add("5");
            WillReturn.Add("5 1 2 3 6");
            WillReturn.Add("14");
            WillReturn.Add("8 7 1 4 3 5 4 1 6 8 10 4 6 5");
            WillReturn.Add("5");
            WillReturn.Add("1 3 5 1 3");
            WillReturn.Add("0");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        for (int I = 1; I <= InputList.Count - 1; I += 2) {
            int[] WArr = InputList[I].Split(' ').Select(pX => int.Parse(pX)).ToArray();
            Solve(WArr);
        }
    }

    static void Solve(int[] pWArr)
    {
        int UB = pWArr.GetUpperBound(0);

        // 最大除去数[区間Sta , 区間End] なDP表
        int[,] DPArr = new int[UB + 1, UB + 1];

        // 幅でループ
        for (int LoopWidth = 2; LoopWidth <= pWArr.Length; LoopWidth++) {
            // 区間Staでループ
            for (int LoopStaInd = 0; LoopStaInd <= UB; LoopStaInd++) {
                int EndInd = LoopStaInd + LoopWidth - 1;
                if (EndInd > UB) break;

                // パターン1 両端と、その間の区間を取り除けるか？
                bool CanAllRemove = true;
                if (Math.Abs(pWArr[LoopStaInd] - pWArr[EndInd]) > 1) {
                    CanAllRemove = false;
                }
                if (LoopWidth > 2) {
                    if (DPArr[LoopStaInd + 1, EndInd - 1] < LoopWidth - 2) {
                        CanAllRemove = false;
                    }
                }

                if (CanAllRemove) {
                    DPArr[LoopStaInd, EndInd] = LoopWidth;
                    continue;
                }

                // パターン2 区間を分ける
                for (int LoopMid = LoopStaInd; LoopMid <= EndInd - 1; LoopMid++) {
                    DPArr[LoopStaInd, EndInd] =
                        Math.Max(DPArr[LoopStaInd, EndInd],
                        DPArr[LoopStaInd, LoopMid] + DPArr[LoopMid + 1, EndInd]);
                }
            }
        }
        Console.WriteLine(DPArr[0, UB]);
    }
}

解説

区間DPで解いてます。