第6回PAST I 魚釣り

問題へのリンク

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("5 6");
            WillReturn.Add("4 5 1 2 6 9");
            WillReturn.Add("1 3 3 2 7 4");
            WillReturn.Add("8 3 7 6 2 1");
            WillReturn.Add("7 8 3 3 7 5");
            WillReturn.Add("8 4 5 5 5 6");
            //9
            //16
            //23
            //30
            //36
            //41
            //45
            //48
            //52
            //53
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[,] BanArr = CreateBanArr(InputList.Skip(1));
        int UB_X = BanArr.GetUpperBound(0);
        int UB_Y = BanArr.GetUpperBound(1);

        long UB_Cnt = UB_X + 1 + UB_Y + 1 - 1;

        // 最大合計[X座標,Y座標,取得数]なDP表
        long[, ,] DPArr = new long[UB_X + 1, UB_Y + 1, UB_Cnt + 1];

        DPArr[0, 0, 0] = 0;
        DPArr[0, 0, 1] = BanArr[0, 0];

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                for (int LoopCnt = 0; LoopCnt <= LoopX + 1 + LoopY + 1 - 1; LoopCnt++) {
                    // 配るDP
                    Action<long, long, long, long> UpdateAct = (pX, pY, pCnt, pNewVal) =>
                    {
                        if (DPArr[pX, pY, pCnt] < pNewVal) {
                            DPArr[pX, pY, pCnt] = pNewVal;
                        }
                    };

                    long CurrVal = DPArr[LoopX, LoopY, LoopCnt];

                    if (LoopY + 1 <= UB_Y) {
                        // 遷移先の数値を使用しない場合
                        UpdateAct(LoopX, LoopY + 1, LoopCnt, CurrVal);

                        // 遷移先の数値を使用する場合
                        long NewVal = CurrVal + BanArr[LoopX, LoopY + 1];
                        UpdateAct(LoopX, LoopY + 1, LoopCnt + 1, NewVal);
                    }

                    if (LoopX + 1 <= UB_X) {
                        // 遷移先の数値を使用しない場合
                        UpdateAct(LoopX + 1, LoopY, LoopCnt, CurrVal);

                        // 遷移先の数値を使用する場合
                        long NewVal = CurrVal + BanArr[LoopX + 1, LoopY];
                        UpdateAct(LoopX + 1, LoopY, LoopCnt + 1, NewVal);
                    }
                }
            }
        }

        for (int LoopCnt = 1; LoopCnt <= UB_Cnt; LoopCnt++) {
            Console.WriteLine(DPArr[UB_X, UB_Y, LoopCnt]);
        }
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をintの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static int[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new int[0, 0];
        }

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

        SplitAct(StrList[0]);

        int UB_X = IntArr.GetUpperBound(0);
        int UB_Y = StrList.Count - 1;

        int[,] WillReturn = new int[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[Y]);
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = IntArr[X];
            }
        }
        return WillReturn;
    }
}

解説

最大合計[X座標,Y座標,取得数]なDP表
を配るDPで更新してます。

遷移先座標ごとに、遷移先座標の数値を使うケースと、使わないケースの
2通りの遷移があります。