Educational DP Contest N Slimes

問題へのリンク

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 20 30 40");
            //190
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("10 10 10 10 10");
            //120
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("1000000000 1000000000 1000000000");
            //5000000000
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("6");
            WillReturn.Add("7 6 8 6 1 1");
            //68
        }
        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);

        // 最小コスト[区間Sta , 区間End] なDP表
        long[,] DPArr = new long[UB + 1, UB + 1];
        for (long I = 0; I <= UB; I++) {
            for (long J = 0; J <= UB; J++) {
                DPArr[I, J] = (I == J ? 0 : long.MaxValue);
            }
        }

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

                if (LoopWidth == 2) {
                    DPArr[LoopStaInd, EndInd] = mAArr[LoopStaInd] + mAArr[EndInd];
                    continue;
                }
                for (long LoopMid = LoopStaInd; LoopMid <= EndInd - 1; LoopMid++) {
                    long LeftLen = LoopMid - LoopStaInd + 1;
                    long RightLen = EndInd - LoopMid;

                    long LeftRangeSum = GetRangeSum(LoopStaInd, LoopMid);
                    long RightRangeSum = GetRangeSum(LoopMid + 1, EndInd);

                    long NewCost = LeftRangeSum + RightRangeSum +
                        DPArr[LoopStaInd, LoopMid] + DPArr[LoopMid + 1, EndInd];
                    DPArr[LoopStaInd, EndInd] = Math.Min(DPArr[LoopStaInd, EndInd], NewCost);
                }
            }
        }
        Console.WriteLine(DPArr[0, UB]);
    }

    // 閉区間を引数として、区間和を返す
    static long GetRangeSum(long pSta, long pEnd)
    {
        long WillReturn = 0;
        for (long I = pSta; I <= pEnd; I++) {
            WillReturn += mAArr[I];
        }
        return WillReturn;
    }
}

解説

最初に、幅1のコストは0、
幅2以上のコストは、long.MaxValue
としてから、区間DPを行ってます。