ABC175-E Picking Goods

問題へのリンク

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("2 2 3");
            WillReturn.Add("1 1 3");
            WillReturn.Add("2 1 4");
            WillReturn.Add("1 2 5");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 5 5");
            WillReturn.Add("1 1 3");
            WillReturn.Add("2 4 20");
            WillReturn.Add("1 2 1");
            WillReturn.Add("1 3 4");
            WillReturn.Add("1 4 2");
            //29
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 5 10");
            WillReturn.Add("2 5 12");
            WillReturn.Add("1 5 12");
            WillReturn.Add("2 3 15");
            WillReturn.Add("1 2 20");
            WillReturn.Add("1 1 28");
            WillReturn.Add("2 4 26");
            WillReturn.Add("3 2 27");
            WillReturn.Add("4 5 21");
            WillReturn.Add("3 5 10");
            WillReturn.Add("1 3 10");
            //142
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

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

        SplitAct(InputList[0]);
        long R = wkArr[0];
        long C = wkArr[1];

        long UB_X = C - 1;
        long UB_Y = R - 1;

        // アイテムの価値[座標のハッシュ値]なDict
        var VDict = new Dictionary<int, long>();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long CurrR = wkArr[0] - 1;
            long CurrC = wkArr[1] - 1;
            long CurrV = wkArr[2];
            int Hash = GetHash(CurrC, CurrR);
            VDict[Hash] = CurrV;
        }

        // アイテムの価値合計の最大値[X座標 , Y座標 , 該当行でのアイテム取得数] なDP表
        long[, ,] DPArr = new long[UB_X + 1, UB_Y + 1, 3 + 1];
        DPArr[0, 0, 0] = 0;

        if (VDict.ContainsKey(0)) {
            DPArr[0, 0, 1] = VDict[0];
        }

        for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {

                int Hash1 = GetHash(LoopX, LoopY + 1);
                long Val1 = 0;
                if (VDict.ContainsKey(Hash1)) {
                    Val1 = VDict[Hash1];
                }

                int Hash2 = GetHash(LoopX + 1, LoopY);
                long Val2 = 0;
                if (VDict.ContainsKey(Hash2)) {
                    Val2 = VDict[Hash2];
                }

                for (long I = 0; I <= 3; I++) {
                    // 1個以上で価値合計0なら、0個で価値合計0のほうが良いので枝切り
                    if (I >= 1) {
                        if (DPArr[LoopX, LoopY, I] == 0) {
                            break;
                        }
                    }

                    Action<long, long, long> UpdateAct = (pNewX, pNewY, pItemVal) =>
                    {
                        if (UB_X < pNewX) return;
                        if (UB_Y < pNewY) return;

                        long NewI = I;
                        if (LoopY < pNewY) { // 縦移動の場合
                            NewI = 0;
                        }

                        if (pItemVal > 0) {
                            NewI++;
                            if (NewI > 3) return;
                        }
                        long NewVal = DPArr[LoopX, LoopY, I] + pItemVal;

                        if (DPArr[pNewX, pNewY, NewI] >= NewVal) {
                            return;
                        }
                        DPArr[pNewX, pNewY, NewI] = NewVal;
                    };

                    // アイテムの取得有無と、
                    // 右に移動と下に移動で、
                    // 4通りの遷移がある

                    UpdateAct(LoopX, LoopY + 1, 0);
                    UpdateAct(LoopX + 1, LoopY, 0);

                    if (Val1 > 0) {
                        UpdateAct(LoopX, LoopY + 1, Val1);
                    }
                    if (Val2 > 0) {
                        UpdateAct(LoopX + 1, LoopY, Val2);
                    }
                }
            }
        }
        long Answer = long.MinValue;
        for (long I = 0; I <= 3; I++) {
            Answer = Math.Max(Answer, DPArr[UB_X, UB_Y, I]);
        }
        Console.WriteLine(Answer);
    }

    // 座標のハッシュ値を返す
    static int GetHash(long pX, long pY)
    {
        return (int)(pX * 10000 + pY);
    }
}

解説

配るDPで解いてます。