ALDS1_10_B: Matrix Chain Multiplication

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q035 連鎖行列積 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            WillReturn.Add("30 35");
            WillReturn.Add("35 15");
            WillReturn.Add("15 5");
            WillReturn.Add("5 10");
            WillReturn.Add("10 20");
            WillReturn.Add("20 25");
            //15125
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct MatrixInfo
    {
        internal int X;
        internal int Y;
    }

    static List<MatrixInfo> mMatrixList = new List<MatrixInfo>();

    static void Main()
    {
        List<string> InputList = GetInputList();

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            MatrixInfo WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            mMatrixList.Add(WillAdd);
        }

        int UB = mMatrixList.Count - 1;

        // 最小の掛け算の数 [開始添字][終了添字] な DP表
        int[,] DPArr = new int[UB + 1, UB + 1];

        // 最大値で初期化
        for (int I = 0; I <= UB; I++) {
            for (int J = 0; J <= UB; J++) {
                DPArr[I, J] = int.MaxValue;
            }
        }

        // 長さ0はコスト0で初期化
        for (int I = 0; I <= UB; I++) {
            DPArr[I, I] = 0;
        }

        // 隣接した行列の積は、事前に求めておく
        for (int I = 0; I <= UB - 1; I++) {
            DPArr[I, I + 1] = mMatrixList[I].X * mMatrixList[I + 1].Y * mMatrixList[I].Y;
        }

        // 計算する積の長さでループ
        for (int I = 2; I <= mMatrixList.Count; I++) {
            // 積の開始の添字でループ
            for (int J = 0; J <= UB - 1; J++) {
                if (J + I - 1 > UB) {
                    break;
                }
                // 左括弧の長さでループ
                for (int LeftLen = 1; LeftLen <= I - 1; LeftLen++) {
                    int LeftSta = J;
                    int LeftEnd = J + LeftLen - 1;
                    int RightSta = LeftEnd + 1;
                    int RightEnd = LeftSta + I - 1;

                    int NewCost = DPArr[LeftSta, LeftEnd] + DPArr[RightSta, RightEnd];
                    NewCost += mMatrixList[LeftSta].X * mMatrixList[LeftEnd].Y * mMatrixList[RightEnd].Y;
                    if (DPArr[LeftSta, RightEnd] > NewCost) {
                        DPArr[LeftSta, RightEnd] = NewCost;
                    }
                }
            }
        }
        Console.WriteLine(DPArr[0, UB]);
    }

    static void PrintArr(int[,] DPArr)
    {
        for (int I = 0; I <= DPArr.GetUpperBound(0); I++) {
            for (int J = 0; J <= DPArr.GetUpperBound(1); J++) {
                if (DPArr[I, J] == int.MaxValue) continue;

                Console.Write("DPArr[{0},{1}]={2},", I, J, DPArr[I, J]);
            }
            Console.WriteLine();
        }
    }
}

解説

最小の掛け算の数 [開始添字][終了添字]
を区間DPで更新してます。